Семинар №4
Тема: Регулярные языки и конечные автоматы.
Цель: 1. научиться писать регулярные выражения для разных языков
2. научиться по автомату строить регулярное выражение и наоборот.
Задачи: 1) освоить понятие регулярного языка, выражения;
2) понять теорему о совпадении классов автоматных и регулярных языков;
3) решение примеров.
Время: 1 пара (2x45 мин).
Место проведения: НГУ, ауд.307а.
Метод: семинар.
Ход семинара:
Учебные | Действия | Действия |
0. проверяю дом. задание | Хожу между рядами и смотрю, как выполнены задания, есть ли вопросы по выполнению, были ли непонятные моменты | Вопросы. |
1. Определение регулярного языка | Даю определение регулярного языка, поясняю, как его проще записать в виде регулярного выражения. Поясняю какие можно делать операции с языками (пример операции, которую нельзя применять). Задачи: 1, 2, 3, 4. | Вспоминают, записывают. Вопросы. |
2. теорема о совпадении классов | Напоминаю теорему о связи языков и языков, распознаваемых конечными автоматами. Привожу интересные моменты доказательства. Примеры построения автоматов. Задачи: 5-12. | Вопросы по доказательству. |
4. Окончание | Записываю на доске д/з: 5-12. Объявляю о теме следующего семинара: Нерегулярные языки. | Записывают задачи на дом. |
¥. «А зачем?» | Отвечаю: «Логически мыслить и быть честными интеллектуально (это легко проверяется на экзамене) развитие способности в данных определениях (быстро) сориентироваться, научиться делать логические выводы, связывать одно понятие с другим. Быть терпеливым слушателем. Быть последовательным (не пропускать шаги). Скорость мысли, правильность мысли. Сосредоточение (как поток воды точит камень, так и поток мыслей дробит непонятное на мелкие детали – дифференцирование, анализ). Затем идёт интегрирование добытых знаний, синтез собственного понимания». http://www. softcraft. ru/design/ap/ap01.shtml — об автоматном программировании. | Некоторые спрашивают: «а зачем это вообще всё надо? О. э, автоматы и т. п.» |
В недетерминированных автоматах можно сделать одно конечное состояние (добавить одно и скачки из конечных в это же).
Понятие автомата à для языков (алгоритмическое распознавание)
языки без автоматов
Подведение промежуточных итогов по автоматам и языкам:
По автомату – язык, по языку – автомат. По языку – регулярное выражение. Минимизация состояний…
Пояснение чем отличается запись {Æ} от Æ (или {a} от a, одно из них язык, другое — слово).
Языки алфавита S как подмножества S*, применимы те же операции (теоретико-множественные)
Пересечение: L1 и L2
Объединение: L1 и L2
Дополнение: L Î S, то язык S*\L = {w Î S* : w Í L}=:
.
Операции конкатенации и навешивания звездочки Клини:
Пусть L1;L2 Î S* языки алфавита S.
Конкатенацией языков L1 и L2 называется язык {wv : w Î L1; v Î L2}, то есть язык, словами которого будут конкатенации слов языка L1 со словами языка L2.
Для определения звездочки Клини нам понадобится ввести ряд промежуточных обозначений. Пусть L язык алфавита S. Для каждого натурального числа n определим по индукции язык Ln:
1. L0 = {e};
2. Ln+1 = LnL.
Пусть теперь L* = 
Ln. Мы говорим, что язык L* получается из языка L навешиванием звездочки Клини. Словами языка L* будут всевозможные конкатенации слов языка L. Отметим, что каким бы не был язык L, даже равным пустому множеству, язык L* обязательно содержит пустое слово.
Оперирование множествами L1× L2 – что за язык, в каком алфавите?
Определение Множество регулярных языков: Введём ряд промежуточных подмножеств. Пусть S некоторый фиксированный конечный алфавит. Определим для каждого натурального числа n множество языков Rn:
1. R0 = {Æ} È {{a} : a Î S};
2. Rn+1 = Rn È {L1 È L2 : L1,L2 Î Rn} È {L1L2 : L1,L2 Î Rn} È {L* : L Î Rn}.
Пусть теперь R:= Rn —множество регулярных языков, а его элементы — регулярные языки.
Регулярные языки à регулярные выражения.
Лишние скобки – это не проблема (ассоциативность конкатенации)
Теорема 4 LÍ S* — регулярен ó $ M – конечный автомат: L=L(M);
Задачи:
1. Написать регулярное выражение, задающее следующий язык: 
2. Написать регулярное выражение, задающее язык алфавита S, состоящем из слов чётной длины, в которых встречается ровно 3 буквы a.
3. Написать регулярное выражение, задающее язык алфавита S, состоящего из слов, в которых буква b не встречается два раза подряд.
4. Написать регулярное выражение для языка, состоящего из слов, в которых между двумя ближайшими вхождениями букв b всегда содержится нечётное число букв a.
Построить конечный автомат M такой, что L(M)=L для следующих случаев:
5. Язык L=(0È1)*00(0È1)*.
6. Язык L=(abaÈbab)*a(aab)*.
7. Язык L=a*b(ab)*(aÈbb)È(bb)*.
8. Язык L=(abÈba)(aaÈbbb)*b.
9. Язык L=(bb)*aa(bb)*abÈb(bb)*aa(bb)*aÈe.
Написать регулярное выражение для языка, распознаваемого следующим автоматом: 
