Теоретические вопросы по курсу «Теория автоматов»

1.Начальные языки описания цифровых автоматов. Язык регулярных выражений алгебры событий 2.Начальные языки описания цифровых автоматов. Граф - схемы алгоритмов (ГСА) цифровых автоматов.

3.Начальные языки описания цифровых автоматов. Логические схемы алгоритмов цифровых автоматов.

4.Начальные языки описания цифровых автоматов. Матричные схемы алгоритмов (МСА) цифровых автоматов.

5.Начальные языки описания цифровых автоматов. Объединение ГСА с помощью МСА

6.Автоматные языки описания цифровых автоматов. Таблицы переходов и выходов.

7.Автоматные языки описания цифровых автоматов. Графы переходов автоматов

8.Автоматы Мура, Мили и С-автоматы.

9.Эквивалентные автоматы, преобразования автоматов.

10.Абстрактный автомат. Соединение двух автоматов: параллельное соединение. Пример.

11.Абстрактный автомат. Соединение двух автоматов последовательное. Пример.

12.Абстрактный автомат. Соединение автоматов с обратной связью. Пример.

13.Абстрактный автомат. Сети и коллективы автоматов

14.Не полностью определенные автоматы

15.Структурный синтез микропрограммных автоматов по ГСА.

16.Формальные языки и операции над ними.

17.Концепция порождения и распознавания.

18.Классификация языков по Хомскому.

19.Конечные автоматы как распознаватели (акцепторы).

20.Машина Тьюринга как автомат, реализующий любые алгоритмы обработки информации

21.Автоматы с магазинной памятью (МП-автоматы).

13. Абстрактный автомат. Сети и коллективы автоматов

Абстраактный автомаат (в теории алгоритмов) — математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени

находящегося в одном состоянии из множества возможных. На вход этому устройству

поступают символы одного алфавита, на выходе оно выдаёт символы (в общем случае) другого алфавита.

Абстрактный автомат

Формально абстрактный автомат определяется как пятерка

Где S — конечное множество состояний автомата, X, Y — конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом, — функция переходов, — функция выходов.

Абстрактный автомат с выделенным начальным состоянием называется инициальным автоматом. Ограничение числа параметров абстрактного автомата определило такое понятие как конечный автомат.

14. Не полностью определенные автоматы

Автомат S называется частичным, или не полностью определенным автоматом, если хотя бы одна из его двух функций не полностью

определена, т. е. для некоторых пар (состояние – вход) значения функций d или l не определены. В автоматной таблице неполная определенность автомата выражается в том, что некоторые ее клетки не заполнены – в них стоят прочерки. В графе частичного автомата в

вершинах, где d не определена, нарушено условие полноты. Для частичных автоматов определения (2.1)–(2.3) нуждаются в изменении. При этом будем пользоваться знаком : запись A B означает, что А и В либо одновременно не определены, либо определены и равны.

Функция d(qi, aj):

а) d(qi, aj) задана таблицей автомата S; б) если d(qi, aj) определена, то

d(qi, aaj)

d(d(qi, a),aj);

(2.5, а)

в) если d(qi, a) не определена, то d(qi, aaj) не определена для всех аj. Функция l(qi, a):

l(qi, aaj)

l (d(qi, a),aj)

(2.5, б)

Автоматное отображение S(qi, a):

а) S(qi, aj) = l (qi, aj) (если l (qi, aj) не определена, то значение S(qi, aj) считается равным прочерку); б) если d(qi, a) определена, то

S(qi, aaj) = S(qi, a)l((qi, a), aj)

(2.6)

(если l((qi, a), aj) не определена, то слово S(qi, aaj) получено из S(qi, a) приписыванием справа прочерка); е) если d(qi, a) не определена, то и S(qi, aaj) не определено.

Входное слово a, для которого S(qi, a) определено, называется допустимым для qi.

Из этих определений видно, что функции переходов и выходов неравноправны: если d не определена на слове a, то она не определена и на всех его продолжениях; для l это не обязательно. Поэтому, если d определена на a, а l не определена на некоторых начальных отрезках a, отображениеS(qi, a) «определено, но не совсем»: оно представляет собой слово,

содержащее прочерки. Эта ситуация естественно интерпретируется на графе: если d не определена на a, то путь a из состояния qi не определен, поэтому неясно, как его продолжить. Если же путь a из qi определен, то, идя по нему, можно

прочесть и выходное слово S(qi, a); ребрам пути a, на которых не написано выходных букв, соответствуют прочерки в слове S(qi, a).

Понятие неотличимости для частичных автоматов также изменяется. Наиболее простым обобщением обычного понятия неотличимости является следующее. Состояние qi автомата S и состояние rj автомата Т называются псевдо-

неотличимыми (псевдоэквивалентными), если для любого a S(qi,a) T(rj, a), т. е.. если область определения qi и rj одна и та же и в этой области qi и rj эквивалентны. Автоматы S и Т псевдонеотличимы, если для любого состояния S найдется

псевдонеотличимое от него состояние Т, и наоборот. Достоинство этого определения в том, что для полностью определенных автоматов оно совпадает с обычным; кроме того, отношение псевдонеотличимости является отношением эквивалентности.

15. Структурный синтез микропрограммных автоматов по ГСА.

16. Формальные языки и операции над ними.

Формальный язык в математической логике и информатике — множество конечных слов (строк, цепочек) над конечным алфавитом.

Определение

Формальный язык может быть определён по-разному, например:

Простым перечислением слов, входящих в данный язык. Этот способ, в основном, применим для определения конечных языков и языков простой структуры.

Словами, порождёнными некоторой формальной грамматикой (см. иерархия Хомского).

Словами, порождёнными регулярным выражением.Словами, распознаваемыми некоторым конечным автоматом.Словами, порождёнными БНФ-конструкцией.

Например, если алфавит задан как , а язык включает в себя все слова над ним, то слово принадлежит . Пустое слово (то есть строка нулевой длины) допускается и часто обозначается как , или .

Некоторые другие примеры формальных языков:

множество , где — неотрицательное число, а означает, что повторяется раз;

множество синтаксически корректных программ в данном языке программирования.

Операции

Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что и являются языками, определёнными над некоторым общим алфавитом.

Конкатенация (сцепление)				содержит все слова, удовлетворяющие форме , где —
это слово из	, а	— слово из		.
Пересечение		содержит все слова, содержащиеся и в			, и в	.
Объединение		содержит все слова, содержащиеся или в			, или в		.
Дополнение языка		содержит все слова алфавита, которые не содержатся в						.
Правое отношение			содержит все слова , для которых существует слово					в
такое, что	находилось в		.

Замыкание Клини содержит все слова, которые могут быть записаны в форме ,

где содержится в и . Следует помнить, что это включает и пустое слово , так как допустимо по условию.

Обращение		содержит обращённые слова из			.
Смешение	и	содержит все слова, которые могут быть записаны в
форме , где				и	являются такими словами, что
связь	находится в		, а	являются такими словами, что
находятся в	.

17. Концепция порождения и распознавания.

Концепция порождения и распознавания.

Автомат-акцептор – это абстракция автомата, при которой он рас сматривает как устройство, которое может отличать конечные последовательности входных данных с помощью своих состояний (концепция распознавания).