从 : x^a y^b x^a 创建一个 DFA
Creating a DFA from : x^a y^b x^a
我不知道如何使用以下语言创建确定性有限自动机：
x^a y^b x^a where a,b >=0
我遇到的主要问题是如何表示反向引用（第二个 x^a）。这两个 x 应该彼此一样频繁。
我该如何编写 DFA 来适应这种情况？
据我了解，我可以在初始状态终止，有零个或多个 x 并终止，有零个或多个 y 然后终止，或零个或 x 并终止，或其中一些或全部然后终止。
这是家庭作业，如有必要，请提供解释，我们将不胜感激。谢谢
有限自动机准确识别 class 常规语言，而您的语言不规则，原因与 Dyck language isn't. You can prove it using the pumping lemma for regular languages 大致相同。由于这是作业，我不会剥夺您实际提出证明的兴奋。
我不知道如何使用以下语言创建确定性有限自动机：
x^a y^b x^a where a,b >=0
我遇到的主要问题是如何表示反向引用（第二个 x^a）。这两个 x 应该彼此一样频繁。
我该如何编写 DFA 来适应这种情况？
据我了解，我可以在初始状态终止，有零个或多个 x 并终止，有零个或多个 y 然后终止，或零个或 x 并终止，或其中一些或全部然后终止。
这是家庭作业，如有必要，请提供解释，我们将不胜感激。谢谢
有限自动机准确识别 class 常规语言，而您的语言不规则，原因与 Dyck language isn't. You can prove it using the pumping lemma for regular languages 大致相同。由于这是作业，我不会剥夺您实际提出证明的兴奋。