如何确定哪种语言更简单
How to determine which language is simpler
以下语言是对更简单语言的补充。
为更简单的语言构造一个 DFA，然后用它给出给定语言的 DFA 状态图，其中 Σ = {a,b}。
L={ w : w 不包含子字符串 baba}。
我不知道哪种语言更简单，谁能解释一下？
我的逻辑与可计算性 class 已经有一段时间了，但我猜补语 Lc 应该是 = { w: w 包含子字符串 'baba'}。
制作一个接受 'baba' 子串的 DFA 可能很容易，您可能只需要状态 firstB、firstA、secondB 和 secondA 等等。
然后制作一个补充 DFA 是微不足道的，只需让接受状态成为非接受状态，反之亦然。
接受任何包含子串 'baba' 的单词的自动机是：
（这是更简单的语言。它的正则表达式是：(a|b)*baba(a|b)*）
我们可以通过将接受状态变为非接受状态来构建补充 DFA，反之亦然，正如您提到的那样：
（必须完成）
以下语言是对更简单语言的补充。 为更简单的语言构造一个 DFA，然后用它给出给定语言的 DFA 状态图，其中 Σ = {a,b}。
L={ w : w 不包含子字符串 baba}。
我不知道哪种语言更简单，谁能解释一下？
我的逻辑与可计算性 class 已经有一段时间了，但我猜补语 Lc 应该是 = { w: w 包含子字符串 'baba'}。
制作一个接受 'baba' 子串的 DFA 可能很容易，您可能只需要状态 firstB、firstA、secondB 和 secondA 等等。
然后制作一个补充 DFA 是微不足道的，只需让接受状态成为非接受状态，反之亦然。
接受任何包含子串 'baba' 的单词的自动机是：
（这是更简单的语言。它的正则表达式是：(a|b)*baba(a|b)*）
我们可以通过将接受状态变为非接受状态来构建补充 DFA，反之亦然，正如您提到的那样：
（必须完成）