找出哪些是正規的語言

我的觀點/回答是，如果y是aregular設置，那麼會退出DFA，它接受年。在L1中存在y = x^n的條件，即x將屬於L1，因爲y被DFA接受。那麼x^n也是x，所以L1是規則的。現在L2 - >這裏的條件是x = y^n。這裏y被DFA接受，所以y^n等於x，所以x可以被DFA接受。這使得L1和L2都正常

我的論點是否正確？

來源

2016-09-17 Anjo

答案有問題，因爲'y'不是一個集合。 – melpomene

我不遵循你的論點。如果有一個接受x^n的DFA，那並不意味着它也必須接受x。 – melpomene

這個問題似乎很不妥。例如，如果我們取A = {a}，那麼L1是語言{a}，L2是語言a *，它們都是常規的。如果我們選擇A = a * b，那麼L1 = a * b（這是規則的）並且L2 = {（a ⁿ b）^m | m，n ≥ 0}，這是不規則的（使用抽象引理）。換句話說，答案取決於答案的選擇。

來源

2016-09-17 17:03:00 templatetypedef

所以沒有任何選項是正確的？ – Anjo

如果A = a * b，則L2 =（a * b）*當然是規則的。詳情請參閱我的回答。 – chazisop

@chazisop你確定嗎？直覺上，L_2是通過選擇A中的單個字符串並複製它們幾次獲得的語言。因此，你不會在L_2中使用aabab，因爲A中沒有固定的字符串，你可以選擇並複製兩次以獲得aabab。 – templatetypedef

找出哪些是正規的語言

回答

相關問題