如何证明任意语言可以被无限状态自动机接受？

Question

我们知道，DFA接受的语言也可以被ISA接受，因为DFA是ISA的一种特殊情况，那么关于任意语言呢？如何证明呢？

Answer 1

定义转义，使语言中的每一个词都有相应的接受状态，达到这些接受状态需要什么支持状态（类似于trie--的结构。https:/en.wikipedia.orgwikiTrie。). 这个自动机是确定性的，可以接受任何语言。