Сборник задач по теории автоматов (стр. 1 )

Сборник задач по теории автоматов

Оглавление

ПРЕДИСЛОВИЕ.......................................................................................................................................................................... 2

Раздел 1. Формальные языки и грамматики.............................................................................................. 3

Занятие 1.1. Формальные языки........................................................................................................................... 3

Занятие 1.2. Формальные системы................................................................................................................... 5

Занятие 1.3. Формальные грамматики........................................................................................................... 6

Занятие 1.4. Контекстно-свободные грамматики............................................................................... 8

Занятие 1.5. Разрешимость языков................................................................................................................. 13

Раздел 2. Основы общей теории автоматов........................................................................................... 19

Занятие 2.1. Машина Тьюринга (МТ)............................................................................................................... 19

Занятие 2.2. Сети Петри............................................................................................................................................. 21

Занятие 2.3. Магазинный автомат (МА)....................................................................................................... 25

Занятие 2.4. Конечный автомат (КА).............................................................................................................. 29

Раздел 3. Конечные автоматы............................................................................................................................ 32

Занятие 3.1. Минимизация автоматов........................................................................................................ 32

Занятие 3.2 Автомат Мура..................................................................................................................................... 35

Занятие 3.3. Детерминация источников..................................................................................................... 36

Раздел 4. структурный синтез автоматов............................................................................................... 39

Занятие 4.1. Синтез комбинационных автоматов............................................................................. 39

Занятие 4.2 Синтез асинхронных автоматов........................................................................................ 42

Занятие 4.3 Синтез синхронных автоматов........................................................................................... 44

СПИСОК ЛИТЕРАТУРЫ...................................................................................................................................................... 47

ПРЕДИСЛОВИЕ

В последнее время инженеры, занимающиеся прикладными исследованиями, все больше используют аппарат теории автоматов. Это объясняется необходимостью создания и эксплуатации современной вычислительной техники, средств передачи и обработки информации, автоматизированных систем управления и проектирования. Наконец, в современной математической науке исследования в областях, традиционно относящихся к дискретной математике (формальные языки и грамматики, общая теория алгоритмов, теория конечных автоматов, трудоемкость вычислений и т. д.), занимают все более заметное место.

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

Данное учебное пособие включает методы решения ряда практических задач. Рассмотрен практический аспект проектирования дискретных устройств. Материал, приведенный в учебном пособии, разбит на введение и четыре раздела. Во введении рассматриваются предмет и метод теории автоматов, на неформальном уровне вводятся основные понятия, обсуждается концепция порождения и распознавания. В первом разделе рассматриваются задачи из области формальных языков и грамматик. Второй раздел посвящен основам общей теории алгоритмов. В третьм разделе изучаются конечные автоматы, а в четвертом - теоретические основы проектирования дискретных устройств.

При написании учебного пособия в значительной мере использовался опыт чтения автором курса по теории автоматов на инженерно-техническом факультете Приднестровского государственного университета им. .

Раздел 1. Формальные языки и грамматики

Занятие 1.1. Формальные языки

Задача 1

Задан алфавит и строка над этим алфавитом. Перечислить префиксы, суф­фиксы и подстроки строки . Оценить, сколькими способами для строки дли­ной можно выбрать суффикс, префикс и подстроку.

Решение

1.  Множество префиксов .

Множество суффиксов .

Множество подстрок .

2.  Подсчитаем число префиксов произвольной строки .

Префиксов длиной может быть .

Префиксов длиной может быть .

. . .

Префиксов длиной может быть .

Префиксов длиной может быть .

Тогда .

3.  Аналогично находим ().

4.  Оценим число подстрок произвольной строки .

Тогда .

Фиксируем -й знак строки в качестве начального знака подстроки и получаем подстрок.

Фиксируем -й знак строки в качестве начального знака подстроки и получаем подстрок.

. . .

Фиксируем -й знак строки в качестве начального знака подстроки и получаем подстроку.

Тогда

Получаем:

Задача 2

Пусть задан алфавит . Определить перечислением язык с длиной строк . Подсчитать число строк языка при произвольном .

Решение

1.  .

2.  Подсчитаем число строк языка при , где – натуральное число, .

Строк длиной может быть .