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

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

Грамматики типа 3 определяются следующим образом:

w1 --> w2

Где w1 – нетерминал, а w2 – следующий формат:

w2 = aB
w2 = a

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

w1 = S
S --> lambda

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


regex computer-science grammar regular-language
person AraK    schedule 21.05.2010    source источник
comment
Вы проверили, есть ли в книге опечатки?   -  person David M    schedule 22.05.2010
comment
@David M Нет, я этого не делал, но сделаю это сейчас. Интересно, что на странице (795) упражнение №19 (i, j) решается именно по этому определению.   -  person AraK    schedule 22.05.2010
comment
Я только что проверил опечатки 6-го изд. и ничего не найдя:highered.mcgraw-hill. com/sites/dl/free/0072880082/299357/   -  person AraK    schedule 22.05.2010

Ответы (1)


arrow_upward
5
arrow_downward

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

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

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

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

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

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

Это не обязательное ограничение.

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

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

person sdcvvc    schedule 21.05.2010
comment
Отличный ответ. Большое спасибо :) - person AraK; 22.05.2010