Обсуждение:Регулярная грамматика
Перейти к навигации
Перейти к поиску
"Любая контекстно-свободная грамматика может быть легко преобразована в вид, в котором правила состоят только из лево-регулярных или право-регулярных (для контекстно-свободных грамматик допустимо наличие тех и других одновременно)."
Это неверное утверждение: из него следует, что классы контекстно-свободных и регулярных языков совпадают. Что имелось в виду?
2A02:2168:84B2:AE00:546F:CA1:6D00:1D3B 17:55, 15 марта 2020 (UTC) гык-sse2
- Видимо имелось в виду, что контекстно-свободная грамматика может быть преобразована в вид, где правила являются смесью лево-регулярных и право-регулярных правил. Однако даже это неверно. Хоть так было сказано в старой версии ангвики, откуда была переведена наша статья, сейчас en:Regular grammar#Mixing left and right regular rules там сказано, что таким образом описываются только en:Linear grammar, правда без источников. В общем я удалил этот кусок. — Алексей Копылов 21:51, 16 марта 2020 (UTC)
P.S. Нашу статью, которая была связана с en:Linear grammar, я выставил на удаление: Википедия:К удалению/16 марта 2020#Праволинейная грамматика. — Алексей Копылов 22:01, 16 марта 2020 (UTC)