automation - DFA的状态图

Question

给出一个 DFA 的状态转移图，它在字母表 {x,y} 上识别以下语言

1. L1= 以 x 开头且长度为奇数的所有字符串的集合
2. L3= 以 x 结尾且长度相等的所有字符串的集合

我需要找到L1 U L3.

这是我的回答：

我的答案的左边部分是L1（也许我可以确保它的正确性），我对它在右边部分的正确性感到困惑，我的答案是否正确？

标签： automationdfa

Answer 1

你的答案是错误的。您可以通过考虑应该使用 DFA 不接受的语言的单词来判断，例如xx，它是一个以 结尾的偶数长度的字符串x，因此它是 的一部分L3。你也失踪了yyyx，这应该是L3.

您想要做的是从一个 epsilon-NFA 开始，其中启动状态有两个 epsilon 转换到L1's 和L3' 启动状态的启动状态。然后使用 NFA-to-DFA 算法得出一个接受L1 U L3.