Распознавать максимальный тип формального языка

Question

В настоящее время я пытаюсь изучать и понимать формальные языки и грамматику. Я понимаю иерархию Хомского, но нашел задачу, в которой я не знаю, как они нашли решение. Задача:

G=({S},{a,b},S,P)
P={S->epsilon, S->aS, S->Sb}

1. Каков максимальный тип этой грамматики?
2. Каков максимальный тип L(G)?

Я знаю, что грамматика типа 2, но в ответе было написано, что L(G) это тип 3.

Кажется, что есть грамматика типа 3, описывающая этот язык, но как вы узнаете, какой максимальный тип формального языка? Есть ли какая-то хитрость?

Answer 1

Я не думаю, что есть какой-то простой, алгоритмический способ всегда сказать, какой класс языка L(G) является; Я имею в виду, в общем, я думаю, что есть случаи, которые просто не могут быть доказаны так или иначе. Это из-за незавершенности / неразрешимости, учитывая, что неограниченные грамматики могут кодировать арифметику. Это очень волнистые.

Эвристически, вы можете попытаться понять, какой у вас язык, вы можете преобразовать грамматику, чтобы сделать грамматику более простой и т. Д., Но это не гарантирует успеха.

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

S -> e
S -> aS
S -> Sb

Любая строка, полученная из S может начинаться с любого количества aс S -> aSи может заканчиваться любым числом bс S -> Sb, Мы могли бы предположить, что язык a*b*, а затем докажите это, показав (1) L(G) является подмножеством ab и (2) ab является подмножеством L (G).

(1) Доказательство проводится по индукции по числу применений S -> aS а также S -> Sb, Базовый случай: если ни один из них не применяется, только строка e выводим. e в a*b*, так что базовый случай подтвержден. Гипотеза об индукции: предположим, что любая строка получена до k применения S -> aS а также S -> Sb в a*b*, Шаг индукции: мы показываем, что любая строка получена с использованием k+1 приложения этих производств также в a*b*, Любая строка, полученная в k+1 производство имеет один полученный в k постановки, пропуская k+1ул производства. Это связано с тем, что постановки сохраняют нетерминальные множества одинаковыми. Мы уже знаем эту более короткую строку, полученную в k приложения в a*b*, У нас есть два случая для рассмотрения:

1. S -> aS: это добавляет один a к передней части более короткой строки в a*b*, держа его в a*b*,
2. S -> Sb: это добавляет один b до конца более короткой строки в a*b*, держа его в a*b*,

Поскольку в обоих случаях строка хранится в a*b*все строки получены в k+1 приложения производств в a*b* и, по индукции, все строки, генерируемые грамматикой.

(2) Рассмотрим любую строку a^n b^m в a*b*, Он генерируется грамматикой следующим образом: n применения A -> aS, m применения B -> Sbи одно приложение S -> e, Таким образом, все строки в a*b* генерируются грамматикой.