Четверг, 13.05.2021, 13:34
Приветствую Вас Гость | RSS | PDA

Всё для студента информата

Полезная информация

Материалы для студента

Всё для студента IT » Материалы для студента » Теория языков программирования

Формальное определение конечного автомата

Мы рассматриваем детерминированный конечный автомат, то есть автомат, который, прочитав любую последовательность входных данных, может находиться только в одном состоянии. Термин «детерминированный» говорит о том, что для всякой последовательности входных символов существует только одно состояние, в которое автомат может перейти из текущего состояния.

ПЕРВЫЙ СПОСОБ ОПИСАНИЯ Конечного Автомата:

А= (Q, ∑, δ, q0, F) – то есть все компоненты автомата описаны синтаксически.

Будем обозначать детерминированный автомат просто двумя символами КА.

Конечный автомат состоит из следующих компонентов:

  1. Конечное множество состояний, обозначаемое как Q.
  2. Конечное множество входных символов, обозначаемое как ∑.
  3. Функция переходов, аргументами которой являются текущее состояние и входной символ, а значением - новое состояние. Функция переходов обозначается как δ. Если q – состояние и а – входной символ, то δ(q, a) – это состояние p, для которого существует дуга, отмеченная символом а и ведущая из q в p.
  4. Начальное состояние, одно из состояний из Q.
  5. Множество заключительных, или допускающих, состояний 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, об остальных элементах этого множества – мы пока ничего не можем утверждать.

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

  1. Была ли прочитана последовательность 01? Если это так, то всякая читаемая последовательность – допустима, т.е. с этого момента автомат будет находиться лишь в допускающих состояниях. Это состояние надо запомнить!
  2. Если последовательность 01 еще не прочитана, то был ли на предыдущем шаге считан символ 0? Если это так, и на данном шаге читается 1, то последовательность 01 будет прочитана, и с этого момента автомат будет находиться только в допускающих состояниях.
  3. Действительно ли последовательность 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) определить КА можно с помощью диаграммы переходов и таблицы переходов.

Похожие статьи:

Не нашли то, что Вам нужно?.. Найдите ответ на форуме!
Категория: Теория языков программирования | Добавил: admin (06.09.2011)
Просмотров: 2735 | Теги: дка, Тяп
Сообщество
Помощь
Форма входа
Поиск

Студенческий помощник по информатике © 2021
При цитировании материалов данного сайта, обязательна ссылка на источник: ITstudents.ru



>