Конечные автоматы

Наиболее распространенными способами конечного задания формального языка являются грамматики и автоматы. Здесь рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам.

Определение 10.1.1. Конечный автомат – это пятерка

M=< Q, A, D, I, F >, где:

а) Q – конечное множество, именуемое множеством состояний, элементы которого называются состояниями и, как правило, либо нумеруются, либо просто обозначаются числами;

б) A – конечный входной алфавит (или просто алфавит);

в) D – конечное подмножество декартового произведения:

DÍ Q´A^*´ Q,

причем элемент множества D вида <p, x, q> – называется переходом из состояния p в состояние q, а слово x – меткой этого перехода;

г) I – конечное множество начальных состояний (IÍ Q);

д) F – конечное множество заключительных (допускающих) состояний (FÍ Q).

Пример 10.1.1. Пусть Q= {1, 2, 3, 4}, A= { a, b }, I= {1}, F= {4}, D ={<1, a,2>, <1, b,3>, <2, a,2>, <2, b,2>, <3, a,3>, <3, b,3>, <2, b,4>, <3, a,4>}. Тогда M₁=< Q, A, D, I, F > – конечный автомат.

Конечные автоматы допускают описание в виде диаграмм состояний (диаграмм переходов). Каждое состояние обозначается кружком, причем начальное состояние распознается по ведущей в него короткой стрелке, а заключительное состояние отмечается двойным кружком. Переходы на диаграмме обозначаются стрелками. Стрелка из состояния p в состояние q, помеченная словом x, фиксирует наличие перехода <p, x, q>.

Например, диаграммаконечного автоматаM₁ имеет следующий вид:

Рис. 10.1.1. Диаграмма переходов конечного автомата М₁

Определение 10.1.2. Путь конечного автомата – это кортеж вида < q₀, < q₀, w₁, q₁ >, q₁, < q₁, w₂, q₂ >, q₂…, q_i-1, < q_i-1, w_i, q_i >, q_i,…q_n>, где n³0 идля всех i < q_i-1, w_i, q_i >Î D, q_i Î Q, w_i Î A^*. При этом:

а) q₀ – начало пути; б) q_n – конец пути;

в) n – длина пути; г) w₁w₂,…, w_i, … w_n – метка пути.

Путь называется успешным, если q₀ Î I, а q_n Î F.

Пример 10.1.2. Рассмотрим конечный автомат М₁ из примера 10.1.1. Путь <1, <1, a, 2>, 2, <2, b, 2>, 2, <2, b, 4>, 4> – успешный.

Меткой этого пути будет слово abb, длина пути равна 3.

Определение 10.1.3. Слово w допускается конечным автоматом М, если оно является меткой некоторого успешного пути.

Пример 10.1.3. Рассмотрим конечный автомат М₁ из примера 10.1.1. Слова abb, abbabbabb, baba, ba – допускаютсяавтоматом М₁, а слова aba, abbabbaba, bab, bbb – недопускаютсяавтоматом М₁.

Определение10.1.4. Множество всех слов, допускаемых конечным автоматом, называется языком, распознаваемым конечным автоматом М. Обозначается этот язык L(M). Также говорят, что автомат М распознает язык L(M).

Пример 10.1.4. Конечный автомат М₁ из примера 10.1.1 распознаетязык L(M₁)= { awb: wÎA^* }È{ bwa: wÎA^* } (заметим, что L(M₁) – представляет собоймножествослов, у которых первая и последняя буквы не совпадают).

Пример 10.1.5. ПустьМ₂=< Q, A, D, I, F >, где Q ={1, 2}, I= {1}, A= {a, b}, F ={1, 2}, D= {<1, a, 2>, <2, b, 1>}. Диаграмма переходов конечного автомата М₂ имеет вид:

Рис. 10.1.2. Диаграмма переходов конечного автомата М₂

Тогда L(M₂)= { (ab)ⁿ: n³0 }È{ (ab)ⁿa: n³0 }.

Определение 10.1.5. Два конечных автомата эквивалентны, если они распознают один и тот же язык.

Пример 10.1.6. Конечныеавтоматы, представленные следующими диаграммами (рис. 10.1.3), эквивалентны.

Рис. 10.1.3. Диаграммы переходов эквивалентных конечных автоматов

Определение 10.1.6. Язык L называется автоматным, еслисуществует конечный автомат, распознающий этот язык.

Определение 10.1.7. Состояние q достижимо изсостояния p, если существует путь, началом которого является p, а концом – q.

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

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

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

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

Определение 10.1.8. Конечныйавтомат M=< Q, A, D, I, F > называется детерминированным, если:

1) множество начальных состояний I содержит ровно один элемент;

2) длина метки каждого перехода равна единице;

3) для любого символа aÎA и для любого состояния pÎQ существует не более одного состояния qÎQ со свойством < p, a, q > ÎD.

Примером детерминированного конечного автомата может служить автомат М₂ из примера 10.1.5. Примером недетерминированного конечного автомата может служить автомат М₁ из примера 10.1.1.

Определение 10.1.9. Детерминированный конечныйавтомат M=< Q, A, D, I, F > называется полным, если для каждого состояния pÎQ и для любого символа aÎA найдется такое состояние qÎQ, что< p, a, q > ÎD.

Теорема 10.1.4. Каждый автоматный язык распознается некоторым полным детерминированным конечным автоматом.

Иными словами, каждому конечному автомату можно сопоставить эквивалентный ему полный детерминированный конечный автомат.

Пример 10.1.7. Диаграмма полного детерминированного конечного автомата, эквивалентного автомату М₁ из примера 10.1.1, выглядит следующим образом:

Рис. 10.1.4. Диаграмма полного детерминированного конечного автомата,

эквивалентного автомату М₁

Пример 10.1.8. Диаграмма полного детерминированного конечного автомата, эквивалентного автомату М₂ из примера 10.1.5, выглядит следующим образом:

Рис. 10.1.5. Диаграмма полного детерминированного конечного автомата,

эквивалентного автомату М₂