Определение регулярных языков
Я попробовал и записал мозг для понимания определения Регулярных языков в дискретной математике и ее Приложениях (Rosen), не достигая цели понимания, почему определение похоже на это в этой книге. На странице (789) я перефразирую определение:
Грамматики типа 3 определяются как:
w1 --> w2
Где w1 является нетерминальным, и w2 имеет форму:
w2 = aB
w2 = a
Где B является нетерминальным, и терминала. Особый случай - когда w1 является начальным символом, и w2 является лямбдой (пустая строка):
w1 = S
S --> lambda
Два вопроса я не мог найти ответ для. Во-первых, Почему не может w2 иметь форму Ba. Во-вторых, Почему лямбда только позволяется для начального символа только. Книга указывает, что, регулярные языки эквивалентны Конечному автомату, и мы можем легко видеть, что мы могут создать FSA для обоих случаев. Я смотрел на другие ресурсы, и эти ограничения не существуют в этих ресурсах.
1 ответ
Во-первых, почему w2 не может иметь форму Ba.
Возьмем следующую грамматику с начальным символом W:
W -> lambda
W -> aX
X -> Wb
она порождает {a n b n : n natural}, который не является обычным языком. Таким образом, это ограничение необходимо, если вы хотите создавать только обычные языки. В качестве альтернативы вы можете разрешить w2 = Ba, но запретить правила вида w2 = aB - это также дает обычные языки. Эта грамматика построит слово «задом наперед».
Если вы разрешите оба типа правил, вы получите класс, известный как линейные языки .
Во-вторых, почему лямбда разрешена только для начального символа.
Это необязательное ограничение.
Вы можете исключить любое использование лямбда для нетерминальных символов: возьмите какое-нибудь правило W -> лямбда, удалите его и замените все правила U -> aW на U -> aW и U -> a. Очевидно, вы не можете исключить использование лямбды для терминального символа (язык больше не будет генерировать пустое слово).
Таким образом, каждая грамматика типа 3, которая использует лямбда во многих местах, может быть «нормализована» до грамматики, которая использует лямбда только для начального символа.