Среди регулярных и контекстно-свободных грамматик, которая является более мощной. Пожалуйста, дайте мне причину тоже
Я просто изучал принципы языков программирования. Я знаю понятия регулярных и контекстно-свободных грамматик и их использование. Но я все еще не могу решить, какой из них более мощный и почему. Пожалуйста помоги
Заранее спасибо.
Решение
Каждый обычный язык не зависит от контекста, но некоторые языки без контекста не являются регулярными. В этом смысле контекстно-свободные языки являются более «мощными», чем обычные языки.
В качестве одного примера нерегулярного языка, который не зависит от контекста, рассмотрим язык всех палиндромов, состоящих из символов x и y. Вы можете доказать, что этот язык нерегулярен, используя лемму накачки или теорему Майхилла-Нерода. Тем не менее, он не зависит от контекста, так как он генерируется грамматикой
S → aSa | bSb | а | б | ε
Интуитивно понятно, что обычные языки соответствуют вопросам «да / нет», которые могут быть решены на компьютере с конечной памятью (теорема Майхилла-Нерода является одним из способов формализации этой интуиции). Это означает, что любая проблема да / нет, которая не может быть решена только с помощью конечной памяти, поэтому не будет соответствовать обычным языкам. Языки без контекста занимают странное промежуточное положение — они соответствуют проблемам, которые могут быть решены на компьютерах с ограниченной памятью и неограниченным стеком.
Если вы хотите узнать больше об этом, я бы рекомендовал прочитать книгу по формальным языкам и вычислимости. Есть много удивительно красивых результатов об этих классах языков, и я никак не могу сжать их в один ответ.
Надеюсь это поможет!
Другие решения