Дискретная математика: теория автоматов
Покупка
Новинка
Тематика:
Дискретная математика
Издательство:
СибГУТИ
Автор:
Овчаренко Алена Юрьевна
Год издания: 2021
Кол-во страниц: 24
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Бакалавриат
Артикул: 824660.01.99
Доступ онлайн
В корзину
Пособие сдержит краткие теоретические сведения, примеры и задания по теории конечных автоматов. Пособие предназначено для проведения практических занятий по теории автоматов при подготовке бакалавров.
Кафедра высшей математики СибГУТИ
Для подготовки студентов по направлениям 09.03.01 «Информатика и вычислительная техника», квалификация (степень) бакалавра, 02.03.02 «Фундаментальная информатика и информационные технологии», квалификация (степень) бакалавра.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 02.03.02: Фундаментальная информатика и информационные технологии
- 09.03.01: Информатика и вычислительная техника
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Министерство цифрового развития, связи и массовых коммуникаций Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Сибирский государственный университет телекоммуникаций и информатики» (СибГУТИ) А. Ю. Овчаренко Дискретная математика: теория автоматов Учебно-методическое пособие Новосибирск 2021
УДК 519.1 Утверждено редакционно-издательским советом СибГУТИ Рецензент: д-р физ.-мат. наук, проф. Д.В. Лыткина Овчаренко А. Ю. Дискретная математика: теория автоматов: Учебно-методическое пособие / А. Ю. Овчаренко; Сибирский государственный университет телекоммуникаций и информатики; каф. высшей математики. – Новосибирск, 2021. – 24 с. Пособие сдержит краткие теоретические сведения, примеры и задания по теории конечных автоматов. Пособие предназначено для проведения практических занятий по теории автоматов при подготовке бакалавров. Кафедра высшей математики СибГУТИ Для подготовки студентов по направлениям 09.03.01 «Информатика и вычислительная техника», квалификация (степень) бакалавра, 02.03.02 «Фундаментальная информатика и информационные технологии», квалификация (степень) бакалавра. © Овчаренко А.Ю., 2021 © Сибирский государственный университет телекоммуникаций и информатики, 2021
Оглавление Введение............................................................................................................... 4 1 Алфавиты и языки............................................................................................ 5 2 Детерминированные конечные автоматы...................................................... 9 3 Регулярные языки и регулярные выражения ..............................................14 4 Минимизация детерминированных конечных автоматов .........................16 Список литературы ...........................................................................................23
Введение Наш курс называется «Теория автоматов и формальных языков». Данный курс является теоретическим. В этом курсе мы будем работать с абстрактными автоматами. Начнём мы с автоматов, распознающих слова (таких как детерминированные и недетерминированные конечные автоматы и автоматы с магазинной памятью), а затем поработаем также и с автоматами, которые способны что-то считать и вычислять (машины Тьюринга, РАМ- машины). Также мы познакомимся с формальными языками и вычислимыми функциями, которые идут рука об руку с вышеперечисленными объектами. Если работа с автоматами зачастую не требует особых теоретических знаний и рассуждений, работа с языками потребует от нас способности мыслить абстрактно и разбираться в доказательствах, поэтому сделаем краткий экскурс в теорию формальных доказательств.
1 Алфавиты и языки Алфавит – непустое конечное множество символов. Обозначение: . Примеры: 0,1 ,a b , ,..., a b z } , ,..., ,.,,,:, , { ;, ... a b z ASCII Unicode Словом (или цепочкой) над алфавитом называется конечная последовательность символов из . Примеры: • 001 • abbab • whale • look! a whale! Пустым словом называется слово, не содержащее ни одного символа. Обозначение: . Множество всех слов над обозначается через * . Пример: 0, 1 , 0, 1, 00, 01, 10, 11, 000, 001, . . . . Замечание 1.1. Символ 0 может обозначать как символ, так и слово, состоящее из одного символа. Но из контекста всегда ясно, о чём именно идёт речь. Длина слова – количество символов, из которых оно состоит. Обозначение: w , где w – слово. Примеры: 001 3 5 abbab !_ _ ! 14 look a whale 0 Обозначим через n множество всех слов длины n над . (Здесь n N – натуральное число.) Примеры: 0,1 • 0
• 1 0,1 • 2 , , , aa bb ab ba Замечание 1.2. 0 1 2 .... Введём также обозначение v w , означающее, что слово v является началом слова w. Например, aab aabab . Пусть v , w – слова. Конкатенацией слов v и w называется слово vw , полученное последовательной записью v и w слева направо. Через nv обозначается слово, полученное конкатенацией слова v с самим собой n раз. Замечание 1.3. Вообще говоря, vw и wv – разные слова. При этом v v v . Примеры: v aba , w bb vw ababb , wv bbaba 2v abaaba , 3 w bbbbbb Формальным языком (или просто языком) над алфавитом называется произвольное подмножество L (не обязательно конечное). Примеры: 0, 1 , 01, 001, 010, 111 L , a b , | n n L a b n N – множество, состоящее из всех слов вида n n a b , где n – натуральное число. Это, например, слова ab , , aabb aaabbb и т. д. 0, 1 , L – множество, состоящее из всех слов, в которых поровну 0 и 1. Это, например, слова , 01, 10, 0101, 0011, 1001 и т. д. , 5 , * , , Замечание 1.4. . Первое множество не содержит вообще ничего, а второе содержит толькопустое слово. Операции над языками. Пусть * ,L K – языки над . L K – пересечение L и K , т. е. множество всех слов, которые лежат и в L , и в K. L K – объединение L и K , т. е. множество всех слов, которые лежат хотя бы в одном из языков L и K . * \ L L – дополнение к L , т. е. множество всех слов над , которые не лежат в L . LK – конкатенация языков L и K , т. е. множество всех слов вида vwvw, где v L , w K . Через nL мы обозначаем конкатенацию
языка L с самим собой n раз. Замечание 1.5. 1) 0 L 2) nL – это не множество слов вида n w , это множество всевозможных конкатенаций 1 2... n w w w , где iw L . * 0 1 2 . . . L L L L – звёздочка Клини, т. е. множество всевозможных конкатенаций слов из L . Примеры: Дано , , a b c , , , , L a b ab abc , , , , K c bc abc . • L K abc • , { , , , } , , L K a b c ab bc abc • , , , , , , , , , , , , , LK a ac abc aabc b bc bbc babc ab abbc ababc abcc abcbc abcabc • , , , , , , , , , , . { . }. L a b ab abc aa aab aabc abb ababc Замечание 1.6. L L L , L L . Контрольные вопросы 1.1 Дайте определение термину алфавит. Приведите примеры. 1.2 Что называется словом над алфавитом. Приведите примеры. 1.3 Что означает пустое слово. 1.4 Чему равна длина слова: a) work b) 10 c) _ ! good morning d) 1.5 Привести примеры множества всех слов длины: a) 0 b) 1 c) 2 1.6 Что называется конкатенацией слов? Если v dd , w aka , то слова будут равны a) vw b) wv c) 2v
d) 3 w e) v f) w 1.7 Дайте определение формальному языку. Приведите пример. 1.8 Какие существуют операции над языками. 1.9 Дан алфавит , , z x c , и слова , , , L z x zx zxc , , , , K c xc zxc . Чему равно: a) L K b) L K c) LK d) L
2 Детерминированные конечные автоматы Детерминированным конечным автоматом (сокращённо ДКА) называется пятёрка 0 , , , , Q q F , где: • Q – множество состояний автомата (конечное); • – алфавит автомата (конечный); • – функция переходов; • 0 q Q – начальное состояние; • F Q – множество заключительных состояний. Конечные автоматы читают слова. – алфавит, над которым задаются эти слова. В процессе чтения слова автомат переходит из одного состояния в другое. Q – множество состояний. Автомат находится в состоянии 0q (старт), когда он начинает последовательно (слева направо) читать буквы слова. Из любого состояния по любой букве алфавита автомат может перейти в какое-то другое состояние в соответствии с функцией переходов . Эта функция действует из множества Q в множество Q, т. е. сопоставляет паре 1, q а из состояния и буквы алфавита некоторое новое состояние 2q . Это сопоставление означает, что, если, находясь в состоянии 1q , автомат прочитает букву a , он перейдёт в состояние 2q . Так он, читая некоторое слово, передвигается по состояниям. Если, дочитав слово до конца, автомат останавливается на одном из состояний из множества F (заключительное состояние), то мы говорим, что данное слово распознаётся (или допускается) данным конечным автоматом. Конечные автоматы удобно изображать в графическом виде (рисунок 2.1). Вершинам соответствуют состояния автомата, а дуги соответствуют функции переходов. Дуга из iq в jq помечена теми входными символами, которые переводят автомат из состояния iq в jq . Стартовое состояние принято обозначать треугольником или стрелкой, входящей в это состояние ниоткуда. Заключительное состояния помечены двойными кружком. Рисунок 2.1 – Пример изображения конечного автомата в виде графа
Замечание 2.1. 1)Слово «функция» в определении детерминированного конечного автомата имеет совершенно конкретный смысл. Оно означает, что для любых состояния 1q Q и символа a существует единственное состояние 2q Q , такое, что 1 2 , q a q . Это означает, что невозможны следующие ситуации: Из какого-то состояния по какой-то букве нет перехода дальше. Из какого-то состояния по одной и той же букве есть несколько переходов. 2)Множество заключительных состояний может быть пустым. Пример 2.1. Построить детерминированный конечный автомат, допускающий (распознающий) все слова над алфавитом 0, 1 , в которых нет двух последовательных единиц. Определить число слов длины k , входящих в L (рисунок 2.2). , 0, 1, 00, 01, 10, 000, 001, 010, 100, 101, 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010, . . . L Рисунок 2.2 – Конечный автомат, распознающий все слова над алфавитом 0, 1 , в которых нет двух последовательных единиц , , , 0, 1 , , , , A A B C A A B , 0 ; , 1 ; , 0 ; , 1 ; , 0 , 1 A A A B B A B C C C C На рисунке 2.3 показана таблица переходов: табличное представление функции . Здесь строки соответствуют состояниям, столбцы – входным символам. Начальное состояние помечено стрелкой, заключительные – звёздочкой. На пересечении строки, соответствующей q , и столбца, соответствующего a, находится , q a . Если – функция переходов, то – расширенная функция переходов. Расширенная функция переходов ставит в соответствие состоянию q и слову w состояние p , в которое автомат попадает из состояния q , обработав
последовательность символов w. Рисунок 2.3 – Пример представления функции в таблице переходов Определим по индукции. Базис. , q q . Шаг индукции. Пусть w – слово вида xa . Тогда , , , q w q x a . Здесь w – слово, a – символ. Соглашение: . . . , , , , w x y z – слова. , , , . . . a b c – символы. Расширенная функция переходов вычисляется по состоянию q и входному слову 1 2 . . . n a a a , следуя пути, который начинается в q и проходит последовательно по дугам, помеченным символами 1 2 . . . n a a a . Пример 2.2. На рисунке 2.4 изображена таблица, которая задает таблицу переходов: табличное представление функции . Рисунок 2.4 – Табличное представление функции , 011 , 01 , 1 , 0 , 1 , 1 , 1 , 1 , 1 B B B A B C Пусть 0 , , , , A Q q F – детерминированный конечный автомат. Языком автомата A называется множество 0 | , L A w q w F . Язык – это множество цепочек, приводящих автомат из состояния 0q в одно из заключительных состояний. Если язык L есть ( ) L A для некоторого детерминированного конечного автомата A , то L – регулярный язык.
Доступ онлайн
В корзину