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

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) является подмножеством b и (2) a b является подмножеством 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* генерируются грамматикой.