regular-language - 我们如何区分常规语言和上下文无关语言？

Question

为了表达常规语言，我们使用正则表达式，对于上下文无关语言，我们可以使用类似堆栈的内存，我知道上下文无关语言有一些规范，例如中心嵌入，但我仍然不确定我们什么时候可以确信给定语言是上下文自由语言？例如为什么自然语言不是常规语言。除了中心嵌入还有什么原因吗？

Answer 1

自动机理论指出，常规语言可以由有限状态机 (FSM) 处理。但是，如果一种语言具有“中心嵌入”，则该语言是上下文无关语言（CFL），需要下推自动机（PDA）。

重要的是，PDA 是一种 FSM，它具有类似存储器的设备的附加资源，该设备是“堆栈”或“计数器”，以便跟踪嵌入。

维基百科用非上下文无关的语言说：-

为了证明给定语言不是上下文无关的，可以使用 the pumping lemma上下文无关语言或许多其他方法，例如Ogden's lemma或Parikh's theorem。

维基百科在决定一种语言是否是常规语言中说：-

为了证明一种语言不规则，人们经常使用 Myhill-Nerode 定理或泵引理等方法。

为什么自然语言不是常规语言？

乔姆斯基在（1957）中说：“英语不是常规语言”。至于上下文无关语言，“我不知道英语本身是否确实超出了此类分析的范围”。

我补充说English is such a vast language which can't be recognised by a finite machine。