Мы рассматриваем детерминированный конечный автомат, то есть автомат, который, прочитав любую последовательность входных данных, может находиться только в одном состоянии. Термин «детерминированный» говорит о том, что для всякой последовательности входных символов существует только одно состояние, в которое автомат может перейти из текущего состояния.
ПЕРВЫЙ СПОСОБ ОПИСАНИЯ Конечного Автомата:
А= (Q, ∑, δ, q0, F) – то есть все компоненты автомата описаны синтаксически.
Будем обозначать детерминированный автомат просто двумя символами КА.
Конечный автомат состоит из следующих компонентов:
- Конечное множество состояний, обозначаемое как Q.
- Конечное множество входных символов, обозначаемое как ∑.
- Функция переходов, аргументами которой являются текущее состояние и входной символ, а значением - новое состояние. Функция переходов обозначается как δ. Если q – состояние и а – входной символ, то δ(q, a) – это состояние p, для которого существует дуга, отмеченная символом а и ведущая из q в p.
- Начальное состояние, одно из состояний из Q.
- Множество заключительных, или допускающих, состояний F ⊆ Q.
Итак, КА – это кортеж А= (Q, ∑, δ, q0, F), где А – имя автомата, Q – множество состояний, ∑ - множество входных символов, δ – функция переходов, q0 – начальное состояние, F – множество допускающих (конечных) состояний.
Как КА обрабатывает входные цепочки
Выясним – что значит выражение «КА решает “допустить” последовательность входных символов.
«Язык» КА – это множество всех его допустимых цепочек.
Пусть а1, а2, …, an – последовательность входных символов. КА начинает работу в состоянии q0. Чтобы определить в каком состоянии окажется КА после обработки первого символа а1, требуется обратиться к функции переходов δ. Пусть, например, δ(q0, a1)=q1. Для следующего входного символа а2 находим δ(q1, а2). Пусть это будет состояние q2. Аналогично находятся и последующие состояния q3, q4, …, qn. Если qn принадлежит F, то входная последовательность а1, а2, …, аn допускается, в противном случае «отвергается» как недопустимая.
ДРУГОЙ СПОСОБ ОПИСАНИЯ Конечного Автомата:
L(KA) = {w | P(w)} – то есть описывается множество цепочек языка данного автомата
Пример 1. Определить формально КА – есть автомат, допускающий цепочки из 0 и 1, которые содержат в себе подцепочку 01. Этот язык описывается как
{w | w имеет вид x01y, где x и y – цепочки, состоящие только из 0 и 1}.
Эквивалентное описание:
{x01y | x и y - некоторые цепочки из 0 и 1 }.
Цепочки этого языка L – есть: 01, 11101000, и т.д.
Цепочки, не принадлежащие этому языку – 10, 1110, 11111, и т.д.
Начальный анализ автомата КА, допускающего цепочки языка L: (1) - ∑ = {0, 1}; (2) – множество состояний автомата Q - содержит начальное состояние q0, об остальных элементах этого множества – мы пока ничего не можем утверждать.
Наши рассуждения о том, какие состояния должен иметь КА, чтобы успешно решить задачу выделения допустимых ячеек. Выделим ряд условий:
- Была ли прочитана последовательность 01? Если это так, то всякая читаемая последовательность – допустима, т.е. с этого момента автомат будет находиться лишь в допускающих состояниях. Это состояние надо запомнить!
- Если последовательность 01 еще не прочитана, то был ли на предыдущем шаге считан символ 0? Если это так, и на данном шаге читается 1, то последовательность 01 будет прочитана, и с этого момента автомат будет находиться только в допускающих состояниях.
- Действительно ли последовательность 01 еще не прочитана, и на предыдущем шаге на вход либо ничего не подавалось (начальное состояние), либо был считан символ 1? В этом случае автомат не перейдет в допускающее состояние до тех пор, пока им не будут считаны 0 и сразу за ним 1.
Порядок появления списка состояний автомата - следующий: выполнение каждого условия à есть новое состояние.
Условие 3 – эквивалентно состоянию q0.
Для состояния q0 имеем – δ(q0, 1)= q0 и если читается 0, то мы попадаем в условие 2. То есть δ(q0, 0)= q2.
Для состояния q2 имеем - δ(q2, 0)= q2, а наличие на входе 1 приводит к состоянию, удовлетворяющему условию 1. То есть переход в допускающее состояние из q2 в q1при входном символе 1: δ(q2, 1)=q1.
Переходы в состоянии q1: δ(q1, 0)= δ(q1, 1)= q1.
Таким образом : Q = {q0, q1, q2}
Полное описание автомата, допускающего язык L цепочек, содержащих 01 в качестве подцепочки, имеет вид: А = ({q0, q1, q2}, {0, 1}, δ, q0, {q1}).
Кроме формальной записи в виде А= (Q, ∑, δ, q0, F) определить КА можно с помощью диаграммы переходов и таблицы переходов.
Похожие статьи:
