设计一个接受几个字符串的 NFA

Question

我需要帮助设计一个接受“hello”、“hello world”和“stay Together”等词的 NFA。字母表包括英文字母、数字和符号。我需要入门帮助。有人有什么建议吗？

Answer 1

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

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

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

由于它只是一堆串联（h-e-l-l-o...）和一些联合（那些“|”字符表示并集），最终的 nfa 将如下所示（如果您想单独处理每个字母，则需要更多串联） :

注意：上图是从 here 生成的，适用于正则表达式 h|hw|st