Среди регулярных и контекстно-свободных грамматик, которая является более мощной. Пожалуйста, дайте мне причину тоже

Я просто изучал принципы языков программирования. Я знаю понятия регулярных и контекстно-свободных грамматик и их использование. Но я все еще не могу решить, какой из них более мощный и почему. Пожалуйста помоги

Заранее спасибо.

-1

Решение

Каждый обычный язык не зависит от контекста, но некоторые языки без контекста не являются регулярными. В этом смысле контекстно-свободные языки являются более «мощными», чем обычные языки.

В качестве одного примера нерегулярного языка, который не зависит от контекста, рассмотрим язык всех палиндромов, состоящих из символов x и y. Вы можете доказать, что этот язык нерегулярен, используя лемму накачки или теорему Майхилла-Нерода. Тем не менее, он не зависит от контекста, так как он генерируется грамматикой

S → aSa | bSb | а | б | ε

Интуитивно понятно, что обычные языки соответствуют вопросам «да / нет», которые могут быть решены на компьютере с конечной памятью (теорема Майхилла-Нерода является одним из способов формализации этой интуиции). Это означает, что любая проблема да / нет, которая не может быть решена только с помощью конечной памяти, поэтому не будет соответствовать обычным языкам. Языки без контекста занимают странное промежуточное положение — они соответствуют проблемам, которые могут быть решены на компьютерах с ограниченной памятью и неограниченным стеком.

Если вы хотите узнать больше об этом, я бы рекомендовал прочитать книгу по формальным языкам и вычислимости. Есть много удивительно красивых результатов об этих классах языков, и я никак не могу сжать их в один ответ.

Надеюсь это поможет!

3

Другие решения


По вопросам рекламы [email protected]