4. Иерархия языков по Хомскому

Определение 9.4.1. Формальный язык называется языком типа 0, если он порождается некоторой грамматикой типа 0.

Определение 9.4.2. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой типа 1) называется порождающая грамматика, каждое правило которой имеет вид B, где BN, , (NA)^*,  (NA)⁺.

Определение 9.4.3. Формальный язык называется контекстным языком, если он порождается контекстной грамматикой (грамматикой типа 1).

Определение 9.4.4. Контекстно-свободной грамматикой (бесконтекстной грамматикой, грамматикой типа 2) называется порождающая грамматика, каждое правило которой имеет вид B, где BN, (NA)^*.

Пример 9.4.1. Пусть N={S, U, T}, A={a, b, c}, P={SUT, UaU, U, TbTc, T}. Тогда G=<N, A, P, S> – контекстно-свободная грамматика, порождающая язык

L(G)={aⁿb^mc^m: n0, m0}

Определение 9.4.5. Формальный язык называется контекстно-свободным языком, если он порождается контекстно-свободной грамматикой (грамматикой типа 2).

Определение 9.4.6. Праволинейной грамматикой (рациональной грамматикой, грамматикой типа 3) называется порождающая грамматика, каждое правило которой имеет вид Bw или BwT, где B, TN, wA^*.

Определение 9.4.7. Формальный язык называется праволинейным языком, если он порождается праволинейной грамматикой (грамматикой типа 3).

Классы формальных языков типа 0, 1, 2, 3 образуют иерархию Хомского. При этом следует иметь в виду, что:

1) каждая праволинейная грамматика является контекстно-свободной грамматикой;

2) каждая контекстно-свободная грамматика без правил вида  является контекстной грамматикой;

3) каждая контекстная грамматика является порождающей грамматикой типа 0.

Пример 9.4.2. Пусть N={S, H}, A={a, b}, P={SaS, Sa, SH, HbH, Hb}. Тогда G=<N, A, P, S> – праволинейная грамматика, порождающая язык L(G)={aⁿb^m: n1 или m1}.

Лекция № 10. Праволинейные языки и конечные автоматы

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

2. Характеризация праволинейных языков

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

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

Определение 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. Диаграмма полного детерминированного конечного автомата,

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