Лекция № 10. Праволинейные языки и конечные автоматы
Иерархия языков по Хомскому
Определение 9.4.1. Формальный язык называется языком типа 0, если он порождается некоторой грамматикой типа 0.
Определение 9.4.2. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой типа 1) называется порождающая грамматика, каждое правило которой имеет вид hBq®haq, где BÎN, h,qÎ (NÈA)*, aÎ (NÈA)+.
Определение 9.4.3. Формальный язык называется контекстным языком, если он порождается контекстной грамматикой (грамматикой типа 1).
Определение 9.4.4. Контекстно-свободной грамматикой (бесконтекстной грамматикой, грамматикой типа 2) называется порождающая грамматика, каждое правило которой имеет вид B®a, где BÎN, aÎ(NÈA)*.
Пример 9.4.1. Пусть N={S, U, T}, A={a, b, c}, P={S®UT, U®aU, U®e, T®bTc, T®e}. Тогда G=<N, A, P, S> – контекстно-свободная грамматика, порождающая язык
L(G)={anbmcm: 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) каждая контекстно-свободная грамматика без правил вида a®e является контекстной грамматикой;
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)={anbm: n³1 или m³1}.
1. Конечные автоматы
2. Характеризация праволинейных языков
Наиболее распространенными способами конечного задания формального языка являются грамматики и автоматы. Здесь рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам.
Определение 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>}. Тогда M1=<Q, A, D, I, F> – конечный автомат.
Конечные автоматы допускают описание в виде диаграмм состояний (диаграмм переходов). Каждое состояние обозначается кружком, причем начальное состояние распознается по ведущей в него короткой стрелке, а заключительное состояние отмечается двойным кружком. Переходы на диаграмме обозначаются стрелками. Стрелка из состояния p в состояние q, помеченная словом x, фиксирует наличие перехода <p, x, q>.
Например, диаграммаконечного автоматаM1 имеет следующий вид:
Определение 10.1.2. Путь конечного автомата – это кортеж вида <q0, <q0, w1, q1>, q1, <q1, w2, q2>, q2…, qi-1, <qi-1, wi, qi>, qi,…qn>, где n³0 идля всех i <qi-1, wi, qi>ÎD, qiÎQ, wiÎA*. При этом:
а) q0 – начало пути; б) qn – конец пути;
в) n – длина пути; г) w1w2,…, wi, … wn– метка пути.
Путь называется успешным, если q0ÎI, а qnÎF.
Пример 10.1.2. Рассмотрим конечный автомат М1 из примера 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. Рассмотрим конечный автомат М1 из примера 10.1.1. Слова abb, abbabbabb, baba, ba – допускаютсяавтоматом М1, а слова aba, abbabbaba, bab, bbb – недопускаютсяавтоматом М1.
Определение10.1.4. Множество всех слов, допускаемых конечным автоматом, называется языком, распознаваемым конечным автоматом М. Обозначается этот язык L(M). Также говорят, что автомат М распознает язык L(M).
Пример 10.1.4. Конечный автомат М1 из примера 10.1.1 распознаетязык L(M1)={awb: wÎA*}È{bwa: wÎA*} (заметим, что L(M1) – представляет собоймножествослов, у которых первая и последняя буквы не совпадают).
Пример 10.1.5. ПустьМ2=<Q, A, D, I, F>, где Q={1, 2}, I={1}, A={a, b}, F={1, 2}, D={<1, a, 2>, <2, b, 1>}. Диаграмма переходов конечного автомата М2 имеет вид:
Определение 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.
Примером детерминированного конечного автомата может служить автомат М2 из примера 10.1.5. Примером недетерминированного конечного автомата может служить автомат М1 из примера 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. Диаграмма полного детерминированного конечного автомата, эквивалентного автомату М1 из примера 10.1.1, выглядит следующим образом:
Рис. 10.1.4. Диаграмма полного детерминированного конечного автомата,
эквивалентного автомату М1
Пример 10.1.8. Диаграмма полного детерминированного конечного автомата, эквивалентного автомату М2 из примера 10.1.5, выглядит следующим образом:
Рис. 10.1.5. Диаграмма полного детерминированного конечного автомата,
