automata - 设计接受几个字符串的 nfa

Question

我需要帮助设计一个接受单词“hello”、“hello world”和“stay together”的 nfa，字母表包括英文字母表、数字和符号。我需要帮助开始。有人有什么建议吗？

Answer 1

我会从一个正则表达式开始，然后从那里开始。

您的问题的正则表达式是：你好 | 你好世界| 呆在一起（记住“你好”是多余的，但你没有指定它需要是最佳的）

然后我们可以使用构造规则将正则表达式转换为nfa。看起来这里解释得很好

因为它只是一堆连接（你好...）和一些联合（那些'|'字符表示联合），最终的 nfa 将如下所示（如果您想单独处理每个字母，则需要更多连接）：

注意：上面的图像是从这里生成的，用于正则表达式 h|hw|st