Характеризация праволинейных языков
Теорема 10.2.1. Каждый автоматный язык является праволинейным.
Доказательство. Пусть автоматный язык L (M) определяется конечным автоматом М=< Q, A, D, I, F >, где QÇA=Æ, и I ={ q0 }. Положим N=Q, S=q0, P ={ p®xq: < p, x, q >Î D }È{ p®e: p Î F }. Тогда G=< N, A, P, S > – праволинейная грамматика (грамматика типа 3), порождающая язык L (M).
Теорема доказана.
Теорема 10.2.2. Каждый праволинейный язык является автоматным.
Доказательство. Без ограничения общности можно считать, что праволинейный язык L задан праволинейной грамматикой, не содержащей правил вида T®u, где uÎA+. Положим:
Q=N, I= { S }, F ={ TÎN: (T®e) ÎP }, D ={< T, u, B >: (T®uB) ÎP }.
Тогда конечный автомат М=< Q, A, D, I, F > порождает такой язык L (M), что L=L (M).
Теорема доказана.
Пример 10.2.1. Праволинейный язык
L ={ w Î{ a, b } *: ç w ç amod 2 =0, ç w ç bmod 2 =0}
порождается грамматикой G=< N, A, P, S >, где N ={ S, T, E, F }, A={ a, b }, P ={ S®aT, S®bE, S®e, T®aS, T®bF, E®aF, E®bS, F®aE, F®bD }.
Диаграмма переходов конечного автомата M3, порождающего этот же язык имеет вид:
Рис. 10.2.1. Диаграмма конечного автомата М3
Определение 10.2.1. Праволинейная грамматика, в которой каждое правило имеет вид T®e, T®a, T®aU, где T, UÎN, aÎA, называется праволинейной грамматикой в нормальной форме (автоматной грамматикой, регулярной грамматикой).
Теорема 10.2.3. Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.
Теорема 10.2.4. Классправолинейныхязыков замкнутотносительно итерации, конкатенации и объединения.
Теорема 10.2.5. Классправолинейныхязыков замкнутотносительно дополнения и пересечения.
Теорема 10.2.6. Пусть L – праволинейный язык над алфавитом А. Тогда найдется такое натуральное p >0, что для любого слова wÎL ç w ç³ p можноподобрать слова x, y, zÎA*, длякоторых справедливы соотношения :y¹e, ç xy ç£ p, xyz=w, xyizÎL (для всех i ³0).
Пример 10.2.2. Пустьязык L= { abnan: n ³0} задан над алфавитом A={a, b}.
Пусть p – произвольноенатуральное число. Положим w=abpap.
Если положить x=e, то возможны следующие варианты:
| y | Z | w | xyyz |
| a | bpap | xyz | aabpapÏL |
| abk(0<k<p) | bp-kap | xyz | abkabpapÏL |
| abp | ap | xyz | abpabpapÏL |
| abpak(0<k£p) | ap-k | xyz | abpak+1bpapÏL |
Как видно из приведенной таблицы, при любом натуральном p и x=e слово xyyzÏL. С помощью а налогичных выкладок можно придти к выводу о том, что при любом натуральном p и при x=a слово xyyzÏL. Этотже вывод оказываетсяверен и при x=abk, x=abpak. В свою очередь, это означает, что условие теоремы 10.2.6 не выполняется, а потому язык L не является автоматным.
Порождающие грамматики
Определение 9.3.1. Порождающей грамматикой (грамматикой типа 0) называется четверка G=< N, A, P, S >, где:
а) N – конечный алфавит, называемый нетерминальным (вспомогательным) алфавитом, символы которого будем обозначать прописными латинскими буквами;
б) А – конечный алфавит, именуемый основным (терминальным) алфавитом, символы которого будем обозначать строчными латинскими буквами;
в) АÇN=Æ;
г) P – конечное подмножество декартового произведения:
PÌ (N È A)+ ´ (N È A)*,
при этом пары (a, b)Î P называются правилами подстановки (просто правилами или продукциями) и записываются в виде a®b;
д) S – нетерминальный символ (S Î N), называемый начальным символом.
Пример 9.3.1. Пусть N ={ S }, A= { a, b }, P ={ S®abS, S ®a }. Тогда G=< N, A, P, S > – является порождающей грамматикой.
Определение 9.3.2. Пусть дана порождающая грамматика G=< N, A, P, S >. Говорят, что слово v непосредственно выводимо из слова w (пишут wÞ v), если w=h a q, v=h b q принекоторыхсловахa, b, h, q в алфавите N È A иa®bÎ P.
Пример 9.3.2. Пусть N ={ S }, A= { a, b }, P ={ S®abS, S ®a }. G=< N, A, P, S > –порождающая грамматика.
Тогда SÞ abS, SÞa, abSÞaba, abSÞ ababS, ababSÞababa.
Определение 9.3.3. Пусть дана порождающая грамматика G. Говорят, что слово wn выводимо из слова w0 (пишут w0 
wn), если
w0Þ w1Þw2Þ…Þwn (n³0).
Пример 9.3.3. Пусть N ={ S }, A= { a, b }, P ={ S®abS, S ®a }. G=< N, A, P, S > – порождающая грамматика.
Тогда S a, S aba, S ababa, S a(ba)m, abS ababS и т.д.
Определение 9.3.4. Множество L (G)={ wÎA*: S w } называется языком, порождаемым грамматикой G=< N, A, P, S >. Также говорят, что грамматика G порождает язык L (G).
Пример 9.3.4. Пусть N ={ S }, A= { a, b }, P ={ S®abS, S ®a }. G1=< N, A, P, S > – грамматика, порождающая язык
L (G1)={ a(ba)m: m³0 }.
Пример 9.3.5. Пусть N ={ S, F }, A= { a, b }, P ={ S®FF, F®aFb, F®ab }. G2=< N, A, P, S > – грамматика, порождающая язык
L (G2)={ anbnambm: n³1, m³1 }.
Определение 9.3.5. Две грамматики называются эквивалентными, если они порождают один и тот же язык.
Пример 9.3.6. Пусть N ={ S, F }, A= { a, b }, P ={ S®aF, F®baF, F®e }. G3=< N, A, P, S > – грамматика, порождающая язык
L (G3)={ a(ba)m: m³0 }.
Грамматика G3 эквивалентна грамматике G3 (см. пример 9.3.4).
Понятие формального языка
Определение 9.1.1. Конечное непустое множество называется алфавитом, его элементы называются символами (буквами).
Определение 9.1.2. Конечная последовательность символов алфавита A называется словом в алфавите A.
Пример 9.1.1. Пусть A= { а, б, в }. Тогда баба, ваб, ббб – слова в алфавите A, при этом осмысленность слов не предполагается.
Определение 9.1.3. Слово, не содержащее ни одного символа, называется пустым и обозначается e.
Множество всех слов в алфавите А будем обозначать А*, а через А+ – множество всех непустых слов.
Определение 9.1.4. Число символов в слове w называется длиной слова w и обозначается ÷ w ÷. Длина пустого слова по определению равна нулю.
Определение 9.1.5. Конкатенацией слов x и y называется слово, обозначаемое как xy (или x×y) и получающееся в результате приписывания слова y в конец слова x.
Если w – слово, то через wn (n=1, 2, …) обозначается слово:
(при n=0 полагается, что wn= e), а через ÷ w ÷а – число вхождений буквы а в слово w.
Так как
,
а множество слов данной длины конечно, то множество А* счетно.
Определение 9.1.6. Любое подмножество L множества А* (LÍ А*) называется формальным языком (языком) над алфавитом А.
Определение 9.1.7. Язык А* – L называется дополнением языка L относительно алфавита А.
Так по определению любой формальный язык представляет собой множество, то над языками, заданными над одним и тем же алфавитом, можно обычным образом определить операции объединения, пересечения и разности.
Пример 9.1.1. Пусть над алфавитом А= { a, b } заданы формальные языки L 1={(ab)n: n³0 } Í А* и L 2={ ambm: m³0 } Í А*. Тогда пересечением этих языков будет язык L 1Ç L 2={e, ab } Í А*.
Задача 9.1.1. Пусть над алфавитом А= { a, b } заданы формальные языки L 1={ w Î А*:÷ w ÷=3} Í А* и L 2={ w Î А*:÷ w ÷а = 1} Í А*. Сколько слов содержитязык L 1 – L 2.
Решение. Язык L 1 содержит 8 слов из трех букв: aaa, aab, aba, abb, baa, bab, bba, bbb. Буква а ровно один раз входит в 3 слова: abb, bab, bba. Таким образом, язык L 1 – L 2 содержит 5 слов.
Конечные автоматы
Наиболее распространенными способами конечного задания формального языка являются грамматики и автоматы. Здесь рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам.
Определение 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.1. Диаграмма переходов конечного автомата М1
Определение 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.2. Диаграмма переходов конечного автомата М2
Тогда L(M2)= { (ab)n: n³0 }È{ (ab)na: 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.
Примером детерминированного конечного автомата может служить автомат М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. Диаграмма полного детерминированного конечного автомата,
эквивалентного автомату М2
Операции над языками
Определение 9.2.1. Конкатенацией языков L 1, L 2 Í А* называется язык L 1× L 2={ xy: xÎL1, yÎL2 }.
Определение 9.2.2. Пусть LÍА*. Тогда L0= { e }, L1=L, Ln+1= Ln × L (n=1, 2, …).
Пример 9.2.1. Пусть А= { a, b }, L= { aa, ab }. Выпишем все слова языка L2 в следующей таблице:
| aa | ab | |
| aa | aaaa | aaab |
| ab | abaa | abab |
Заметим, что L2= {(aa) n (ab) m (aa) k: m, n³0, m+n+k=2 }.
Слова языка L3 могут быть получены следующим образом:
| aa | ab | |
| aaaa | aaaaaa | aaaaab |
| abaa | abaaaa | abaaab |
| aaab | aaabaa | aaabab |
| abab | ababaa | ababab |
Попутно заметим, что L3¹ {(aa) n (ab) m (aa) k: m, n³0, m+n+k=3 }, поскольку ababab Ï{(aa) n (ab) m (aa) k: m, n³0, m+n+k=3 }.
Определение 9.2.3. Итерацией языка L называетсяязык
.
Пример 9.2.2. Если А ={ a, b } и L= { aa, ab, ba, bb }, то:
L*= { w Î A*: ç w ç mod 2=0 }.
Определение 9.2.4. Обращением (зеркальным образом) слова w называется слово, записанное теми же буквами в обратном порядке (обозначается w R).
Например, если w=abab, то w R= baba.
Определение 9.2.5. Пусть LÍA*. Тогда язык L R={ w R: wÎ L } называется обращением языка L.
Пример 9.2.3. Если А ={ a, b } и L= { aa, ab, ba, bb }, то L R= L.
Пример 9.2.4. Если А ={ a, b } и L= { anbm : n³1, m³1 }, то L R={ bman : n³1, m³1 }.
Определение 9.2.5. Пусть А1 и А2 алфавиты. Отображение H: A1*® A2*, удовлетворяющее условию H(u×w)=H(u)×H(w) для любых u, wÎ A1*, называется гомоморфизмом (морфизмом).
Очевидно, каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.
Пример 9.2.5. Пусть А ={ a, b }. Определим гомоморфизм H: A*®A* равенствами H(a)=b, H(b)=a. Тогда H(aaabb)=bbaaa и т.д.