DFA状态图

Question

给出DFA的状态转换图，以识别字母表{x，y}上的下列语言

1. L1 =以x开头并具有奇数length
2. L3 =以x结尾并具有偶数长度

的所有字符串的集合

我要找到L1 U L3。

这是我的回答：

​

​

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

Answer 1

你的回答是错误的。您可以通过考虑使用DFA不接受的语言来判断，例如xx，它是以x结尾的偶数长度字符串，因此它是L3的一部分。您还缺少了yyyx，它应该是L3的一部分。

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