Теория конечных автоматов

 

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

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

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

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

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

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

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

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

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

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

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

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

Пример. Разберем работу контроллера, проверяющего четно или нечетно число единиц в произвольной цепочке, состоящей из нулей и единиц. Допустим, что соответствующий конечный автомат должен « допускать» все цепочки, содержащие нечетное число единиц и « отвергать » цепочки с четным их числом. Назовем этот автомат « контроллером четности ». Считаем, что символы, отличные от 0 и 1 нельзя подавать на вход автомата. Итак, входной алфавит контроллера есть множество {0, 1} . Считаем, что в конкретный момент времени конечный автомат имеет дело лишь с одним входным символом, а информацию о предыдущих символах входной цепочки сохраняет с помощью конечного множества состояний. В качестве множества состояний будем рассматривать множество { чет, нечет }, одно из этих состояний должно быть выбрано в качестве начального. Пусть им будет состояние {чет}, поскольку на первом шаге число прочитанных единиц равно нулю, а нуль есть четное число. При чтении очередного входного символа состояние автомата либо меняется, либо сохраняется прежним причем новое его состояние зависит от входного символа и текущего состояния. Такое изменение состояния называется переходом.

Работа автомата может описываться математически функцией переходов вида d( Sтек., x ) = Sнов. Иначе это можно записать следующим образом:

d ( чет., 0) = чет. d ( чет., 1) = нечет.

d ( нечет., 0) = нечет. d ( нечет., 1) = чет.

Контроллер имеет единственное допускающее состояние НЕЧЕТ, а ЧЕТ есть « отвергающее » состояние. Отразим последовательность переходов автомата при подаче на его вход цепочки 1101.

ЧЕТ ® НЕЧЕТ ® ЧЕТ® ЧЕТ® НЕЧЕТ

Таблица переходов такого автомата имеет вид:

 

чет	чет	нечет
нечет	нечет	чет

 

Определение. Конечный автомат — это формальная система

S = { A, Q, d, l,V },

объекты которой следующие:

* A — конечное множество входных символов (множество

терминалов);

* Q — конечное множество внутренних состояний автомата

(множество нетерминалов);

* V — конечное множество выходных символов (выходной алфавит);

* d — функция переходов, для которой характерно A ´ Q ® Q;

* l — функция выходов, определяющая отображение вида :

A ´ Q ® V.

 

Национально-культурная автономия в РФ

⇐ Предыдущая78910111213141516Следующая ⇒

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

Национально-культурная автономия основывается на принципах:

свободного волеизъявления граждан при отнесении себя к определенной этнической общности;

самоорганизации и самоуправления;

многообразия форм внутренней организации национально-культурной автономии;

сочетания общественной инициативы с гос.

поддержкой;

уважения языка, культуры, традиций и обычаев граждан различных этнических общностей;

законности.

Национально-культурная автономия имеет право:

· получать поддержку со стороны органов государственной власти и органов МСУ, необходимую для сохранения национальной самобытности, развития национального (родного) языка и национальной культуры;

· создавать СМИ в порядке, установленном законодательством РФ, получать и распространять информацию на национальном (родном) языке;

· сохранять и обогащать историческое и культурное наследие, иметь свободный доступ к нац. культурным ценностям;

· создавать образовательные и научные учреждения, учреждения культуры и обеспечивать их функционирование в соответствии с законодательством РФ;

· участвовать через своих полномочных представителей в деятельности м/н неправительственных организаций;

Местные НКА граждан РФ, относящих себя к определенной этнической общности, могут образовывать региональную национально-культурную автономию граждан РФ, относящих себя к определенной этнической общности; учреждается на общем собрании (сходе); учредителями могут быть граждане РФ, зарегистрированные общественные объединения граждан РФ.

Региональные НКА двух и более субъектов РФ могут создавать органы межрегиональной координации своей деятельности. Такие органы не являются межрегиональными национально-культурными автономиями. Федеральная НКА граждан РФ, относящих себя к определенной этнической общности, учреждается не менее чем половиной зарегистрированных региональных национально-культурных автономий граждан РФ, относящих себя к определенной этнической общности. Образование, государственная регистрация, реорганизация и (или) ликвидация национально-культурной автономии осуществляются в соответствии с ФЗ, ФЗ от 19.05.1995 (в редакции ФЗ от 02.11.2004) «Об общественных объединениях» и иными ФЗ.

Порядок приема в члены НКА определяется уставом соответствующей национально-культурной автономии.

Вопрос (какой-то). Избирательное право: понятие, структура, нормативная база

Избирательное право (в субъективном, узком смысле слова) – конституционное право граждан избирать и быть избранными в выборные органы, государственные и муниципальные органы власти и право участвовать в референдуме.

Избирательное право (в объективном, широком смысле слова) – совокупность правовых норм, регулирующих весь комплекс избирательных процессов в РФ, включая избирательные права граждан.

Избирательное право в узком смысле слова включает в себя: 1) пассивное избирательное право граждан РФ (право быть избранными в органы государственной и муниципальной власти); 2) активное избирательное право граждан РФ (право избирать в выборные органы власти).

Активное избирательное право принадлежит каждому гражданину РФ, достигшему 18 лет, но с учетом установленных федеральными законами ограничений. Не могут избирать граждане РФ: 1) признанные вступившим в законную силу решением суда недееспособными (ограниченно дееспособными); 2) в отношении которых вступил в законную силу приговор суда за совершение преступления, наказанием за которое назначено лишение свободы.

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

Не может быть избран в органы государственной и муниципальной власти гражданин РФ: 1) занимающий на момент выборов государственную должность, обязанности по исполнению которой несовместимы с выборной должностью; 2) осужденный к лишению свободы приговором суда, вынесенным в установленном порядке; 3) признанный вступившим в законную силу приговором суда недееспособным или ограниченно дееспособным.

Избирательное право как совокупность правовых норм имеет систему: 1) федеральное законодательство о выборах и референдуме; 2) законодательство о выборах и референдуме субъектов РФ.

Элементы системы избирательного права РФ выделяются в зависимости от уровня принятия нормативных актов. Нормативные акты, регулирующие избирательное право: 1) Конституция РФ от 12 декабря 1993 г.; 2) федеральные законы (ФЗ от 12 июня 2002 г. № 67-ФЗ «Об основных гарантиях избирательных прав и права на участие в референдуме граждан Российской Федерации» (с изменениями от 27 сентября, 24 декабря 2002 г., 23 июня, 4 июля, 23 декабря 2003 г.), 3) конституции (уставы) субъектов РФ; 4) законы субъектов РФ; 5) уставы муниципальных образований.

---

⇐ Предыдущая78910111213141516Следующая ⇒

---

Дата добавления: 2016-03-26; просмотров: 627 | Нарушение авторских прав

---

Похожая информация:

Поиск на сайте:

Назад в библиотеку

---

Описание n log n алгоритма минимизации состояний в детерминированном конечном автомате

Автор: Yingjie XU

Перевод: Швец О.С.

Источник: Describing an n log n algorithm for minimizing states in deterministic finite automaton.

Аннотация

Существует несколько хорошо известных алгоритмов для минимизации детерминированных конечных автоматов. В данной работе приведен алгоритм предназначенный для минимизации конечного автомата или для определения эквивалентности двух конечных автоматов. Асимптотическое времени работы алгоритма ограничено с kn log n, где k–некоторая константа, которая линейно зависит от размера входного алфавита, и n–число состояний.

Содержание

1 Введение

2 Предварительные сведения

2.1 ДКА, слово и язык

2.2 Эквивалентные состояния и минимальный ДКА.

3 Минимизация

3.1 Классический алгоритм.

3.2 Алгоритм Хопкрофта

1 Введение

Проблема написания эффективных алгоритмов для нахождения минимального детерминированного конечного автомата, эквивалентного данному автомату может быть прослежена с 1950–х годов в работах Хаффмана[Huf55] и Мура[Moo58]. За это время были предложены альтернативные алгоритмы. Тем не менее, анализ этих алгоритмов указывал на то, что в худшем случае они имеют сложность n₂, где n–число состояний.

Хопкрофт [Hop71] в 1971 г. предложил алгоритм минимизации конечных детерминированных автоматов, сложности O(n log n) с n состояниями.

Коэффициент пропорциональности линейно зависит от количества входных символов. Очевидно, что этот алгоритм может использоваться и для задачи определения, являются ли два конечных автомата эквивалентными. Последние исследования [BC04, BBC08] показали, что они тесно связаны.

Текст организован следующим образом. В разделе 2 мы приведем несколько определений и обозначений, используемых в данной статье. В разделе 3 мы опишем алгоритм Хопкрофта и объясним принцип его работы.

2 Предварительные сведения

2.1 ДКА, слово и язык

Определение 2.1. Детерминированный конечный автомат (ДКА) D задается пятеркой (Q, Σ, δ, q₀, F) где:

• Q – конечное множество состояний;
• Σ – входной алфавит;
• δ: Q×Σ → Q – функция переходов;
• q₀– начальное состояние;
• F ⊆ Q – множество заключительных состояний.

Если функция переходов всюду определена, то автомат D – называется полным.

Определение 2.2. Любая конечная последовательность символов алфавита a ∈ Σ – это слово.

Через Σ* обозначим множество всех слов в алфавите Σ и ε – пустое слово. Определим расширенную функцию перехода : Q×Σ* → Q следующим образом:

Определение 2.3. Язык, принимаемый автоматом D, L(D) – это множество всех слов w ∈ Σ* таких, что .

2.2 Эквивалентные состояния и минимальный ДКА

Для ДКА D = (Q, Σ, δ, q₀, F), два состояния q₁, q₂ Q называются эквивалентными и обозначаются q₁ ≈ q₂, если для любого w∈Σ*, ∈F ↔ ∈F. Два состояния, которые не являются эквивалентными называются различимыми.

Глава 2. Конечные автоматы

Минимальный автомат D/≈, эквивалентный исходному, называется фактор–автоматом, и его состояния соответствуют классами эквивалентности ≈. Доказано, что он уникален с точностью до изоморфизма.

Определение 2.4. Два ДКА D и  эквивалентны, если и только если L(D) = L ().

Определению 2.5. ДКА называется минимальным, если нет другого эквивалентного ему ДКА, с меньшим числом состояний.

3 Минимизация

3.1 Классический алгоритм

Определение 3.1. Состояние q ∈ Q в ДКА D = (Q, Σ, δ, q₀, F) называется достижимым, если (q₀,w) = q, для некоторого w ∈ Σ*.

Определение 3.2. Если все состояния, в Q достижимы, то полный ДКА D называется инициально связным (ИСДКА).

Лемма 3.1. Предположим, что D является ИСДКА. Тогда D – минимальный, если все пары состояний различимы.

Доказательство. (⇒) Это легко видеть, если D имеет два эквивалентных состояния. Тогда одно из них можно удалить, а дуги входящие в это состояние, можно перебросить в другое состояние. Это не повлияет на принимаемую последовательность.

(⇐) Предположим, что в D все состояния являются попарно различимы. Пусть D имеет k состояний. Рассмотреть любые другие  с l<k состояниями. Мы должны показать, что L() ≠ L(D).

Для каждого состояния q автомата D выберем произвольно одну строку w_q такую, что (q₀,w_q) = q. Из предположения следует, что такое w_q существует для каждого q и все состояния являются достижимыми. Так как l < k, то существуют два состояния p ≠ q в D, такие, что в  мы имеем (q₀,w_p) =  (q₀,w_q). Поскольку p и q различимы в D, то существует последовательность w такая, что (q_w) ∈ F, но (q_w) ∉ F (или наоборот, но если это так, то мы всегда можем поменять местами p и q). Это означает, что D принимает w_pw, но не w_qw. Но в  имеем (q₀,w_pw) = (q₀,w_qw), так  либо принимает как w_pw так и w_qw, либо отвергает оба эти слова.

Поэтому L () ≠ L(D), что и требовалось.

Лемма 3.2. Состояние неразличимость является отношением эквивалентности.

Лемма 3.3. Пусть δ(p, a) = p′ и δ(q, a) = q′. Тогда, если p′, q′ различимые, то p, q также различимые.

Чтобы минимизировать автомат A, после удаления недостижимых состояний, мы отыщем все классы эквивалентности с неразличимыми состояниями и объединим их в одном состоянии нового автомата .

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

Алгоритм 1. Классический алгоритм

Исходные данные: Детерминированный конечный автомат A

Результат: Минимальный автомат  эквивалентный А

1: Удалить недостижимые состояния

2: Отметить все пары p, q, где p ∈ F и q ∉ F

3:       repeat

4:             for всех неотмеченных пар p, q do

5:                   for всех символов a do

6:                             if пара δ(p, a), δ(q, a) отмечена then

7:                                     отметить p, q

8:                             end if

9:                   end for

10:        endfor

11: until нет новых пар отмеченных состояний

12: Построить приведенный автомат

Теорема 3.1. Алгоритм минимизации 3.1 правилен, то есть L() = L(A) и  является минимальным.

Доказательство.

Докажем все необходимые условия, одно за другим.

Эквивалентность выполняется. Доказательство легко проводится индукцией по длине кратчайшего слова, различающего p и q при помощи Леммы 3.3.

 корректно определен. Из того факта, что неразличимость является отношением эквивалентности по Лемме 3.2, следует, что состояния в определены корректно.

L() = L(A). Для каждого w имеем (q₀,w) ∈ (,w).Таким образом, по определению заключительных состояний в , автомата  принимает w, если и только если A принимает w.

минимален.

Здесь полезна Лемма 3.1. Это вполне очевидно следует из построения, при котором все состояния различимы.

Теорема 3.2. Время работы Алгоритма 3.1 составляет O(n²).

3.2 Алгоритм Хопкрофта

Лемма 3.4. Пусть D = (Q, Σ, δ, q₀, F) и последовательность ρ_i (i ³ 0) отношений эквивалентности на Q описывается следующим образом:

ρ₀ = {(p, q)|p, q ∈ F}, ∪ {(p, q)|p, q ∈ Q — F},

ρ_i+1 = {(p, q) ∈ ρ_i|(∀a ∈ Σ)(δ(p, a), δ(q, a)) ∈ ρ_i}.

Справедливы следующие утверждения:

• ρ₀ ⊇ ρ₁ ⊇ · · · .

• если ρ_i = ρ_i+1, то ρ_i= ρ_j для всех j > i.

• существует 0 ≤ k ≤ |Q| такой, что ρ_k = ρ_k+1.

Рассмотрим ситуацию, когда ρ_i ≠ ρ_i+1,

ρ_i ≠ ρ_i+1

↔ (∃p,q ∈ Q, a ∈ Σ)(p,q) ∈ ρ_i и (δ(p,a), δ(q,a)) ∉ ρ_i

↔ (∃U∈ Q/ρ_i, a ∈ Σ ) p,q ∈ U и (δ(p,a), δ(q,a)) ∉ ρ_i

↔ (∃U,V ∈ Q/ρ_i, a ∈Σ) p,q ∈ U и δ(p,a) ∈ V и δ(q, a) ∉ V (1)

↔ (∃U,V ∈ Q/ρ_i, a ∈ Σ) δ(U,a) ∩ V ≠ 0< и δ(U,a) ⊄ V

При помощи леммы 3.4, может быть построено отношение эквивалентности на D с помощью алгоритма, приведенного ниже:

Алгоритм 2. Вычисление эквивалентного отношения с помощью уточнения

1: Q/θ ← {F,Q — F}

2: while (∃U,V ∈ Q/θ, a ∈ Σ ) (см. соотношение 1) do

3:          Q/θ ← (Q/θ {U}) U {U ∩ δ^-1(V, a), U — U ∩ δ^-1(V, a)}

4: end while

Пока это довольно абстрактно, и, мы должны решить, как эффективно находить некоторые тройки U, V, a для которых выполняется соотношение 1.

Леммы 3.5. Пусть D = (Q, Σ, δ, q₀, F) и U принадлежат Q/θ. Предположим, что мы разобьем U на U′ и U′′. Тогда для любого a из Σ, разбиение всех классов θ, относительно (U′, a) и (U′′, a) дает тот же результат, как и разбиение θ относительно (U, a), (U′, a) и (U′′, a).

Леммы 3.6. Пусть D = (Q, Σ, δ, q₀, F), Q/θ = {F,Q — F}, a из Σ. Тогда разбиение θ относительно либо (F, a) или (Q – F, a) дает тот же результат, как и разбиение θ относительно их обоих.

Алгоритм 3. Алгоритм Хопкрофта

1: W ← {F,Q − F}

2: W ← {F,Q − F}

3:

4:          выберите и удалите S с W

5:                   forall a из K do

6:                            l_a ← δ⁻¹(S, a)

7:                             forall R иP таких, что R ∩ l_a ≠ ∅ and R ⊄ l_ado

8:                                      раздел R в R1 and R2: R1 ← R ∩ l_aand R2 ←R − R1

9:                             заменить R в Р с R1 и R2

10:                           if R ∈ W then

11:                                    заменить R в W, в R1 и R2

12:                           else

13:                                    if |R1| W |R2| then

14:                                             добавить R1 в W

15:                                    else

16:                                             добавить R2 в W

17:                                    end if

18:                           end if

19:                 end for

20:        end for

21: end while

Леммы 3.5 и 3.6 предоставили возможность сократить вычисления. Алгоритм 3.2 – алгоритм Хопкрофта:

Теорема 3.3. Пусть U = {U₁,U₂, . . . Х_m} (1 ≤ m ≤ |Q|) – множество всех построенных классов, созданных алгоритмом минимизации. Тогда

Теоремы 3.4. Время работы алгоритма 3.2 составляет O(n log n).

Ссылки

[BBC08] Jean Berstel, Luc Boasson, and Olivier Carton. Hopcroft’s automaton minimization algorithm and sturmian words. In DMTCS’2008, volume AI, pages 355–366, 2008.

[BC04] Jean Berstel and Olivier Carton. On the complexity of hopcroft’s state minimization algorithm. In CIAA’2004, volume 3317, pages 35–44, 2004.

[Hop71] J.E. Hopcroft. An n log n algorithm for minimizing states in a _nite automaton. Technical Report CS–71–190, Stanford University, January 1971.

[Huf55] D.A. Hu_man. The synthesis of sequential switching circuits. The Journal of Symbolic Logic, 20(1), 1955.

[Moo58] E.F. Moore. Gedanken–experiments on sequential machines. TheJournal of Symbolic Logic, 23(1), 1958.

Конечные автоматы: примеры решений задач

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

Задачи с решениями: конечные автоматы

Задача 1. Найти минимальный автомат, эквивалентный данному.

Решение задачи на построение минимального конечного автомата

Задача 2. Построить конечный детерминированный автомат (определить множества $S,X,Y$, построить таблицу и диаграмму Мура), построить каноническую таблицу, канонические уравнения. Нарисовать схему устройства, используя логические элементы «И», «ИЛИ», «НЕ».

Построение конечного детерменированного автомата

Задача 3. Автомат задан набором $({а, b}, {q1, q2, q3, q4, q5}, QS , Qf )$, где $\{а, b\}$ – алфавит, $Q_s$ – множество начальных состояний (входов), $Q_f$ – множество конечных состояний (выходов), и списком дуг с метками, определяющих допустимые переходы.
Запись $(i, j, а, b)$ означает, что дуга $(i, j)$, идущая из состояния $q_i$ в состояние $q_j$, имеет две метки – $а$ и $b$.
1. Построить граф автомата и найти язык $L$, допускаемый автоматом.
2. Детерминизировать автомат.
3. Построить графы автоматов, представляющих языки $L_0$, $L \cup L_0$, $L \cdot L_0$ и $L^*$.
4. Из построенных графов удалить $\lambda$-переходы.

Решение задачи о конечном автомате

Задачи с решениями: машины Тьюринга

Задача 1. Последовательность натуральных чисел $(x_1,x_2,…,x_n)$ задается на ленте машины Тьюринга как слово $01^{x_1}01^{x_2}0…01^{x_n}$, где $1^x$ обозначает слово $11…1$, состоящее из $x$ единиц. Предполагается, что остальные клетки ленты содержат нули. Построить машину Тьюринга, осуществляющую заданное преобразование. В начале работы головка показывает на 0 перед крайней левой единицей, и машина находится в состоянии $q_1$.

Решение задачи на построение машины Тьюринга (копирование части слова)

Задача 2. Построить машину Тьюринга, которая вычисляет модуль разности любых двух натуральных чисел.

Математический форум Math Help Planet

Машина Тьюринга: разность чисел

Задача 3. Построить машину Тьюринга, которая вычисляет остаток от деления заданного конструктивного натурального числа на 5.

Машина Тьюринга: остаток от деления на 5

Задача 4. Задать определения: МТ, правильно вычисляющей предикат; МТ, вычисляющая предикат с восстановлением. Построить МТ для правильного вычисления предиката.

Машина Тьюринга: вычисление предиката

Построение конечных автоматов на заказ

Выполняем для студентов решение отдельных заданий, контрольных и практических работ по любым разделам теории конечных автоматов (в том числе написание машин Тьюринга), оказываем помощь в сдаче тестов. Подробное оформление, таблицы, графики, пояснение, использование специальных программ при необходимости. Стоимость примера от 150 рублей, оформление производится в Word, срок от 3 дней.

Все примеры по дискретной математике

Теория конечных автоматов

 

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

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

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

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

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

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

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

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

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

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

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

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

Пример. Разберем работу контроллера, проверяющего четно или нечетно число единиц в произвольной цепочке, состоящей из нулей и единиц. Допустим, что соответствующий конечный автомат должен « допускать» все цепочки, содержащие нечетное число единиц и « отвергать » цепочки с четным их числом. Назовем этот автомат « контроллером четности ». Считаем, что символы, отличные от 0 и 1 нельзя подавать на вход автомата. Итак, входной алфавит контроллера есть множество {0, 1} . Считаем, что в конкретный момент времени конечный автомат имеет дело лишь с одним входным символом, а информацию о предыдущих символах входной цепочки сохраняет с помощью конечного множества состояний. В качестве множества состояний будем рассматривать множество { чет, нечет }, одно из этих состояний должно быть выбрано в качестве начального. Пусть им будет состояние {чет}, поскольку на первом шаге число прочитанных единиц равно нулю, а нуль есть четное число. При чтении очередного входного символа состояние автомата либо меняется, либо сохраняется прежним причем новое его состояние зависит от входного символа и текущего состояния. Такое изменение состояния называется переходом.

Работа автомата может описываться математически функцией переходов вида d( Sтек., x ) = Sнов. Иначе это можно записать следующим образом:

d ( чет., 0) = чет.

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

d ( чет., 1) = нечет.

d ( нечет., 0) = нечет. d ( нечет., 1) = чет.

Контроллер имеет единственное допускающее состояние НЕЧЕТ, а ЧЕТ есть « отвергающее » состояние. Отразим последовательность переходов автомата при подаче на его вход цепочки 1101.

ЧЕТ ® НЕЧЕТ ® ЧЕТ® ЧЕТ® НЕЧЕТ

Таблица переходов такого автомата имеет вид:

 

чет	чет	нечет
нечет	нечет	чет

 

Определение. Конечный автомат — это формальная система

S = { A, Q, d, l,V },

объекты которой следующие:

* A — конечное множество входных символов (множество

терминалов);

* Q — конечное множество внутренних состояний автомата

(множество нетерминалов);

* V — конечное множество выходных символов (выходной алфавит);

* d — функция переходов, для которой характерно A ´ Q ® Q;

* l — функция выходов, определяющая отображение вида :

A ´ Q ® V.

 

банковские карты

электронный кошелек

банковский платеж

денежные переводы

почтовые переводы

платежные терминалы