可以正則語言有一個線性有界自動機

我想了解自動機。每個常規語言都可以有線性有界自動機嗎？

2013-03-30 Paul

可能會更好被問及http://math.stackexchange.com/ – stark

是。 [常規語言是幾乎所有形式語言的子集]（http://stackoverflow.com/questions/13143186/example-of-non-linear-unambiguous-and-non-deterministic-cfl?answertab=votes#tab-top）即使對於上下文敏感的語言，我們也有線性有界自動。 –

是的，對於每種常規語言都可能有線性有界自動機。常規語言是上下文相關語言的真子集。 CSL是與線性有界自動機（LBA）相關的語言。有關正式語法和語言類的層次結構的更多信息，請閱讀Chomsky Hierarchy。

http://en.wikipedia.org/wiki/Chomsky_hierarchy

來源

2013-04-11 18:40:43 Deepu

可以正則語言有一個線性有界自動機

回答

相關問題