从创建DFA：X^AY^BX ^一个

Question

我不知道如何从语言创建一个确定有限自动机：

x^a y^b x^a where a,b >=0 

主要的问题我已经是如何表示反向引用（在第二个x^a）。这两个x应该像彼此一样频繁。

如何编写DFA来适应此问题？

从我所了解的情况来看，我可以在初始状态终止，零个或多个x的终止，有零个或多个y的终止，或零或x的终止，或其中一些或全部，然后终止。

这是家庭作业，所以如果需要的话，如果包括解释，将不胜感激。谢谢。

Answer 1

有限自动机准确地识别正规语言的类，并且您的语言不规则，或多或少与Dyck language不相同的原因。你可以使用pumping lemma for regular languages来证明它。既然这是作业，我不会带走你真正提出证明的兴奋。