人、狼、羊、白菜过河问题.ppt

10 一个人带着狼 山羊和白菜来到一条河边 想要到河对岸去 岸边有一条小船 小船只能装下这个人以及狼 山羊和白菜中之一 如果没有人照看 狼会吃掉山羊 山羊会吃掉白菜 试问它们能不能安全地渡河 如果可能 请用有穷自动机写出渡河的方法 参考答案 能安全地渡河 先定义 人 M 狼 W 山羊 G 白菜 C 字符集为每次渡河的成员 故 M MW MG MC 状态集为河边和对岸的情况 用双竖线表示河 因此 开始状态为 MWGC 接受状态为 MWGC DFA图如下