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

Для примера следует: f1 = v2& v4 V v3 & v1 & v2 V v3 & v4 & v1

Аналогично составляются функции f2, f3, f4.

3. Перечислить способы представления конечного автомата

Конечный автомат – система объектов , в которой , , , Q, T, V – конечные множества (алфавиты), Q - алфавит состояний, Т - входной алфавит, V - выходной алфавит, - функция переходов (определяется как отображение множества в множество , т. е. ), - функция выходов , т. е. отображается на множестве V.

1. Ориентированный граф (граф состояний), в котором состояния - вершины графа, дуги – переходы между состояниями.

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

ai - символы входного алфавита, вызывающие переход;

Vi - символы выходного алфавита;

qi – состояния автомата.

Детерминированным называется автомат, граф перехода которого не содержит вершин, имеющих одинаково помеченные дуги.

2. Таблица переходов

Строки – состояния автомата. Столбцы - символы входного алфавита

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

Пример:

	a1	a2	a3	a4	a5	a6
q1	q2, V1	q3, V2
q2			q4, V3
q3				q5, V4
q4			q5, V5		q5, V6
q5						q6, V7
q6

3. Матрицей переходов

Матрица переходов представляет собой квадратную матрицу, строки и столбцы которой соответствуют внутренним состояниям автомата. Клетки матрицы заполняются входными символами ak ,при которых автомат переходит из состояния qi в состояние qj, а также выходными символами, соответствующими паре (ak, qi).

Пример:

	q1	q2	q3	q4	q5	q6
q1		a1, V1	a2, V2
q2				a3, V3
q3					a4, V4
q4					a3, V5 a5, V6
q5						a6, V7
q6

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

4. Определение недетерминированного и конечного автомата

Теория автоматов лежит в основе теории построения компиляторов. Конечный автомат – одно из основных понятий. Под автоматом подразумевается не реально существующее техническое устройство, хотя такое устройство может быть построено, а некоторая математическая модель, свойства и поведение которой можно имитировать с помощью программы на вычислительной машине. Конечный автомат является простейшей из моделей теории автоматов и служит управляющим устройством для всех остальных видов автоматов. Конечный автомат обладает рядом свойств:

·  конечный автомат может решать ряд легких задач компиляции. Лексический блок почти всегда строится на основе конечного автомата.

·  работа конечного автомата отличается высоким быстродействием.

·  моделирование конечного автомата требует фиксированного объема памяти, что упрощает проблемы, связанные с управлением памятью.

·  Существует ряд теорем и алгоритмов, позволяющих конструировать и упрощать конечные автоматы.

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

Конечный автомат называется полностью определенным, если его таблица переходов не содержит пустых клеток. Иначе автомат называют частично определенным.

Конечный автомат – это формальная система, которая создаётся с помощью следующих объектов:

·  конечным множеством входных символов;

·  конечным множеством состояний;

·  функцией переходов, которая каждой паре (входной символ, текущее состояние) ставит в соответствие новое состояние;

·  начальное состояние;

·  подмножество состояний, выделенных в качестве допускающих или заключительных;

Итак, детерминированным конечным автоматом (ДКА) называется устройство, описываемое следующими параметрами:

Q – конечное множество состояний.

Σ – конечное множество входных символов.

δ – функция перехода. Аргументы – состояние и входной символ, результат – состояние.

q0 – начальное состояние, принадлежит Q.

F – множество допускающих состояний, является подмножеством Q.

И функционирующие следующим образом:

Автомат начинает работу в состоянии q0.

Если автомат находится в состоянии qi, а на вход поступает символ b, то автомат переходит в состояние δ(qi, b).

Определение недетерминированного конечного автомата (НКА) практически полностью повторяет приведённое выше определение ДКА. Отличий всего два:

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

Если автомат находится в состоянии qi, а на вход поступает символ b, то автомат переходит во множество состояний δ(qi, b). Если автомат находится во множестве состояний {qi}, то он переходит во множество состояний, получаемое объединением множеств δ(qi, b).

НКА тоже распознаёт цепочки символов, цепочка считается допустимой, если после её обработки множество состояний, в котором оказался автомат, содержит хотя бы одно допускающее. Таким образом, НКА также задаёт некоторый язык.

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

Алгоритм построения эквивалентного детерминированного конечного автомата.

Приведение недетерминированного автомата к автомату без ε-переходов.

Определение: ε-замыканием состояния s называется множество всех состояний, которые достижимы из s без подачи входного сигнала. Множеством состояний полученного автомата являются ε-замыкания состояний автомата с ε-переходами.

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

Примеры:

ДКА

таблица переходов

		0	1
->	q0	q1	q0
*	q1	q1	q0

НеДКА

таблица переходов

		0	1
->	q0	{ q0,q1}	{q0}
	q1	{q2}	Ø
*	q2	Ø	Ø

5. Программная реализация логических функций

Представление автомата схемой, состоящей из логических элементов наиболее исследованный вид структурной реализации автомата. Другой её вид – реализация программ. Программа реализует логические функции f(x1,x2...,xn) = y, если для любого двоичного набора δ = (δ1,…,δn) при начальном состоянии элементов памяти x1= δ1, x2= δ2,..,xn= δn программа за конечное число шагов останавливается и в ячейке y лежит величина y = f(δ1, δ2,..δn)