Вопросы и упражнения.
Задайте следующие языки над словарём
{0,1} в виде регулярных
выражений. Затем выполните переход от
регулярного выражения к недетерминированному
конечному автомату и детерминированному
конечному автомату.
1. Множество цепочек, оканчивающихся на
01;
2. Множество цепочек, содержащих два
нуля подряд;
3. Множество цепочек, у которых на третьей
позиции справа стоит 1.
Литература
1. Карпов, Ю. Г. Теория автоматов / Ю. Г.
Карпов. – СПб. : Питер, 2002. – 224 с.: ил.
2. Мозговой, М. В. Классика программирования:
алгоритмы, языки, автоматы, компиляторы.
Практический подход / М. В. Мозговой. –
СПб. : Наука и техника, 2006. – 320 с.: ил.
3. Хопкрофт, Джон, Э. Введение в теорию
автоматов, языков и вычислений, 2-е изд.
/ Дж. Э. Хопкрофт, Р. Мотвани, Дж. Д. Ульман
; пер. с англ. – М. : Издательский дом
«Вильямс», 2008. – 528 с.: ил.
25
