Регулярные выражения

Одним из средств записи автоматных грамматик являются регулярные выражения. Определим регулярные выражения следующим образом:

1. e, 0 Î R_V;

2. a Ì V Þ a Î R_V;

3. R₁, R₂ Î R_V, то R₁R₂ Î R_V, R₁+R₂ Î R_V, R₁^* Î R_V, R₂^* Î R_V, где

R₁R₂ – операция склеивания (конкатенация, конъюнкция),

R₁+R₂ – операция объединения (дизъюнкция),

, где Rⁿ= RR…R (n раз).

Теорема Клини: (об эквивалентности составления языка с помощью регулярных выражений и с помощью автоматов): множество всех регулярных выражений и множество всех автоматных языков над одним и тем же словарем совпадают.

Как составить синтаксическую диаграмму по регулярному выражению:

1) Если a элемент из словаря, то ему ставится в соответствие дуга, помеченная символом:

a Þ

2) Если склеены две цепочки a и b, то этой склейке соответствуют две дуги помеченные a и b:

a b Þ

3)

a + b Þ

4)

a^* Þ

Пример: составить все цепочки, состоящие их 0 и 1, такие, что они оканчиваются на 011. Составить язык с помощью регулярных выражений: (0*+1*)*011.

Пример: a = (0+1)*010*(0+1)* - построить граф автомата или синтаксическую диаграмму:

Замечания: следующие утверждения равносильны:

1) L - язык, воспринимаемый конечным недетерминированным автоматом.

2) L - язык, воспринимаемый конечным детерминированным автоматом.

3) L - порожден автоматной грамматикой.

4) L - задан регулярным выражением.

Пример: Б - буква, Ц - цифра, тогда Б(Б+Ц)* - язык идентификатора.

Вопросы и упражнения

Построить синтаксическую диаграмму, описывающую язык

a = (0*+1)*(0+10*)* 0*.

Является ли построенный автомат детерминированным?