АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Конечный автомат и его программная реализация

Читайте также:
  1. GIP-M. АВТОМАТИЗИРОВАННОЕ ПРОЕКТИРОВАНИЕ ДОРОГ
  2. III Механизация, Электрификация и автоматизация сельскохозяйственного производства
  3. А. Автоматическая блокировка – однопутный участок.
  4. Автомат с магазинной памятью
  5. Автоматизация документооборота
  6. Автоматизация документооборота компании
  7. Автоматизация звука в слогах и словах.
  8. Автоматизація виробництва
  9. Автоматизація процедури інвентаризації
  10. Автоматизація та комп'ютерно-інтегровані технології
  11. Автоматизированная информационная система для гостиниц «Отель- Симпл»
  12. Автоматизированная система управления гостиницей «Русский отель»

Распознаватели регулярных грамматик строятся на конечных автоматах. Конечный автомат – это математическая модель, свойства и поведение которой полностью определяются пятеркой: M = (Q, S, δ, q 0, F),

где Q – конечное множество состояний;

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

δ(qi, сk) – функция переходов (qi – текущее состояние, сk – очередной символ);

q 0 – начальное состояние;

F = { qj } – подмножество допускающих состояний.

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

Пример. Автомат «Чет-нечет» описывается следующим образом:

Q = {Чет, Нечет};

S = {0, 1};

δ(Чет, 0) = Чет, δ(Нечет, 0) = Нечет, δ(Чет, 1) = Нечет, δ(Нечет, 1) = Чет;

q 0 = Чет;

F = {Чет}

Строка «10110» приведет такой автомат в состояние Нечет, т. е. будет отвергнута, а строка «110011» – в состояние Чет, т. е. будет принята.

Для представления функции переходов конечного автомата помимо аналитической формы могут использоваться: таблица (см. таблицу 4), граф переходов состояний (см. рисунок 4) и синтаксическая диаграмма (см. рисунок 5).

Таблица 4 – Функция переходов

q s    
Чет Чет Нечет
Нечет Нечет Чет

 

Рисунок 4 – Граф переходов Рисунок 5 – Синтаксическая диаграмма

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

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

Таблица 5 – Дополненная таблица конечного автомата

q с     Символы завершения Другие символы
Чет Чет Нечет Конец Ошибка
Нечет Нечет Чет Ошибка Ошибка

 

Пусть S – строка на входе автомата;

Ind – номер очередного символа;

q – текущее состояние автомата;

Table – таблица, учитывающая символы завершения и другие символы.

Тогда алгоритм работы автомата можно представить следующим образом.

 

Ind:= 1

q:= q 0

Цикл-пока q ¹ «Ошибка» и q ¹ «Конец»

q = Table [ q, S [ Ind ]]

Ind:= Ind +1


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)