Определение регулярных языков

Question

Я пытался и сжигал свой мозг, чтобы понять определение регулярных языков в Дискретная математика и ее приложения (Розен) , не достигнув цели понимания, почему определение в этой книге такое. На странице (789) я перефразирую определение:

Грамматика типа 3 определяется как:

w1 --> w2

Где w1 не является терминалом, а w2 имеет вид:

w2 = aB
w2 = a

Где B не является терминалом, а a является терминалом. Особый случай - когда w1 - начальный символ, а w2 - лямбда (пустая строка):

w1 = S
S --> lambda

Два вопроса, на которые я не смог найти ответ. Во-первых, почему w2 не может иметь форму Ba . Во-вторых, почему лямбда разрешено только для начального символа только . В книге говорится, что обычные языки эквивалентны конечному автомату, и мы легко видим, что мы можем создать FSA для обоих случаев. Я посмотрел на другие ресурсы, и эти ограничения не существуют в этих ресурсах.

Answer 1

Во-первых, почему w2 не может иметь форму Ba.

Взять следующую грамматику с W в качестве начального символа:

W -> lambda
W -> aX
X -> Wb

генерирует {a ⁿ b ⁿ : n натуральный}, который не является обычным языком. Так что это ограничение необходимо, если вы хотите создавать только обычные языки. В качестве альтернативы вы можете разрешить w2 = Ba, но запретить правила вида w2 = aB - это также дает обычные языки. Эта грамматика будет строить слово «назад».

Если вы разрешите оба типа правил, вы получите класс, известный как линейные языки .

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

Это не необходимое ограничение.

Вы можете исключить любое использование лямбды для нетерминальных символов: возьмите некоторое правило W -> лямбда, удалите его и замените все правила U -> aW на U -> aW и U -> a. Очевидно, что вы не можете исключить использование лямбды для терминального символа (язык больше не будет давать пустое слово).

Таким образом, каждая грамматика типа 3, которая во многих местах использует лямбду, может быть "нормализована" к грамматике, которая использует лямбду только для начального символа.