Теории формальных языков

Теория формальных языков.

Формальный язык – множество предложений, которые построены по определенным правилам. Предложения строятся из слов, слова из символов.

Отношение эквивалентности – на множестве А р с (а,а)  с р.а с А – симметричны.

Синтаксис – структура правильных предложений и допустимые структуры текстов программ. Синтаксис определяет корректность программ.

Наиболее используемой в языках программирования форма Бэкуса-Наура (БНФ), впервые была применена для описания языка «Алгол» в 1965г..  БНФ определяющий синтаксис десятичных чисел:

<десятичное число>:<число без знака> ‌‌‌‌‌‌‌‌‌‌‌‌‌│ + <число без знака> │ - <число без знака>

<число без знака> :=  <цифра> │ <число без знака> <цифра>

<цифра> := 0, │1│,…,│9│

В левой части БНФ  в угловых скобках записываются названия определенных синтаксических категорий.

«:=» - «определяется как»

«│» - «или», «сложение».

Правая часть БНФ определяет возможные варианты конструирования, конкретные значения этих категорий.

БНФ содержит алфавит символов, их которых составляют значения. Для десятичных целых чисел это множество «+», «-» и «↔».

Появление БНФ стимулирует развитие  теории формальных языков и ее применения.

Любая прикладная программа, написанная на языке программирования высокого уровня или проблемно-ориентированном языке, должна быть переведена в эквивалентную программу на машинном языке или на языке близком к машинном (AutoCode, Asembдer). 

Транслятор – программа, которая переводит исходную программу в эквивалентную ей объектную.

Компилятор – транслятор, выполняющий перевод с языка высшего уровня в объектную программу.

В языках высокого уровня мы оперируем привычными нм понятиями из математики: «переменная», «выражение», «равенство».

В машинных языках: «поместить в сумматор», «запомнить в ячейке», «адрес», «регистр».

Кроме того одна конструкция языка высокого уровня  соответствует  нескольким компонентам машинного языка. Поэтому например,  программирования скалярного произведения матриц на машинном языке состоит из 100 строк.

Структура компилятора:

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

Фазы компиляции:

1.       Лексический анализ – реализуется часть компилятора, которая называется лексическим анализатором или сканером. Ходом сканера является цепочка символов некоторого алфавита. С точки зрения смысла программы некоторые подцепочки представляют собой определенные объекты, которые должны рассматриваться как единое целое. Такие подцепочки принято называть лексемами.

2.       Синтаксический анализ

3.       Семантический анализ

4.       Генерация кода

5.       Оптимизация кода.

Операции  над языками.

Алфавит – конечное непустое множество, его элементами являются символы, буквы, слова, цепочка, строка.

Рассмотрим алфавит ∑ (baaa). baaa – слово в алфавите  ∑.

∑* - множество всех символов алфавите ∑.

Слово не содержит ни одного символа, т.е. последовательность длины 0, называется пустым словом и обозначается

Множество ∑*  счетное. В самом деле в алфавите ∑ множество всех слов должно быть конечно.  Следовательно, ∑*  объединением счетного числа конечных множеств.

∑+- множество всех непустых слов.

Если ∑ ={а}, то ∑+   = {а,аа,ааа,аааа…}

Если L с ∑+, то L - это формальный язык над алфавитом ∑.

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

Пусть L1, L2  c ∑* , тогда L1* L2 ↔ {xy│x c L1, y c L2  }

           L1* L2  - конкатенация языка L1 и L2                   

Пример:

  Если L1 = {а, abb} и L2 = {bbc,c}, то L1, L2  = {ac,abbc,abbbbc}

Пусть L c ∑* , тогда L0 ↔ {E}, Ln   ↔ L…L (n раз), если n>0

Пример:

L={akbal│0<k<l}, то L2 = { akbal bam │0<k<1<l-1,m>1}

Интеграцией языка L ( обозначается L*) называется язык UncN Ln - звездочка Клана.

Пример:

Если ∑={a;b} L={aa,ab,ba,bb},то L* ={w c ∑* │ │w│ = 2}

Обращением (зеркальным образом слова w, обозначается wR  ) называется слово, в котором символы, состояние слова w идут в обратном порядке.

Пример:

w=baaca, то wR =acaab

Пусть L c ∑*,  тогда  LR  ↔ { wR │w c L}

LR  - обращение L.

х- префикс (начало) слову (х  [ у), если у=xu для некоторого слова U.

Пример:

E [ baa, b [ baa, ba[ baa, baa[baa

Пусть L c ∑*,  тогда через Pref (L) обозначается множество, состоящие из всех префиксов слова языка L:

                            Pref(L) ↔ {x │ ( сущетсвует y c L) x [ y}

Множество Pref(L) – множество префиксов L.

Говорят, что слово х – суффикс(конец) слова у (x]y), если y=ux для некоторого слова u.

Пусть L c ∑*,  тогда через suf (L) обозначается множество, состоящее из всех суффиксов языка L:

Suf(L) ↔ {x │ ( существует y c L) x ] y}

Множество Suf(L) – множество суффиксов языков L.

Говорят, что слово x — подслово (substring) слова y, если y = uxv для некоторых слов u и v.

Пусть L ⊆ У.. Т огда через Subw(L) обозначается множество, состоящее из всех подслов слов языка L. Множество Subw(L) называется множеством подслов языка L.

Слово a1a2 . . . an (длины n >= 0) называется  подпоследовательностью (subsequence) слова y, если существуют такие слова u0, u1,. . . , un, что u0a1u1a2 . . . anun = y.

Замечание. Все подслова слова y являются также подпоследовательностями слова y.

Пусть L ⊆ У.. Т огда через Subseq(L) обозначается множество, состоящее из всех подпоследовательностей слов языка L. Множество Subseq(L) называется множеством под-

последовательностей языка L.

Пример Рассмотрим язык L = {cba, c} над алфавитом {a, b, c}. Очевидно, что Subseq(L) = {ε, a, b, c, ba, ca, cb, cba}.

Функция f : K → L называется биекцией (bijection), если каждый элемент множества L является образом ровно одного элемента множества K (относительно функции f).

Множества K и L называются равномощными (of equal cardinality), если существует биекция из K в L.

Гомоморфизмы

Пусть У1 и У2 — алфавиты. Если отображение h: У.1 → У.2 удовлетворяет условию h(x ・ y) = h(x) ・ h(y) для всех слов x ∈ У.1 и y ∈ У.1, то отображение h называется гомоморфизмом

(морфизмом).

Можно доказать, что если h — гомоморфизм, то h(ε) = ε.

Пример  Пусть У1 = {a, b} и У2 = {c}. Т огда отображение h: У.1 → У.2, заданное равенством h(w) = c2|w|, является гомоморфизмом.

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

Если h: У.1 → У.2 — гомоморфизм и L ⊆ У.1,то через h(L) обозначается язык {h(w) | w ∈ L}.

Пример Пусть У = {a, b} и гомоморфизм h: У. → У. задан равенствами h(a) = abba и h(b) = ε. Тогда h({baa, bb}) = {abbaabba, ε}.

Если h: У.1 → У.2 — гомоморфизм и L ⊆ У.2,то через h-1(L) обозначается язык {w ∈ У.1 | h(w) ∈ L}.

Пример Рассмотрим алфавит У = {a, b}. Пусть гомоморфизм h: У. → У. задан равенствами h(a) = ab и h(b) = abb. Т огда  h-1({ε, abbb, abbab, ababab}) = {ε, ba, aaa}.

Порождающие грамматики

Порождающей грамматикой (грамматикой типа 0, generative grammar, rewrite grammar) называется четвёрка G <_N,У, P, S>, где N и У — конечные алфавиты, N ∩У = .,

P ⊂ (N ∪ У)+ × (N ∪ У)., P конечно и S ∈ N. Здесь У — основной алфавит (терминальный алфавит), его элементы называются терминальными символами или терминалами (terminal), N — вспомогательный алфавит (нетерминальный алфавит), его элементы

называются нетерминальными символами, нетерминалами, вспомогательными символами или переменными (nonterminal, variable),S — начальный символ (аксиома, start symbol). Пары (α, β) ∈ P называются правилами подстановки, просто правилами или продук-

циями (rewriting rule, production) и записываются в виде α → β.

Пример  Пусть даны множества N = {S}, У = {a, b, c},

P = {S → acSbcS, cS → ε}. Т огда _N,У, P, S              является порождающей грамматикой.

Будем обозначать элементы множества Устрочными буквами из начала латинского алфавита, а элементы множества N — заглавными латинскими буквами. Обычно в примерах

мы будем задавать грамматику в виде списка правил, подразумевая, что алфавит N составляют все заглавные буквы, встречающиеся в правилах, а алфавит У — все строчные буквы, встречающиесяв правилах. При этом правила порождающей грамматики записыва-

ют в таком порядке, что левая часть первого правила есть начальный

символ S.

Для обозначения n правил с одинаковыми евыми частями α → β1,. . . , α → βn часто используют сокращённую апись α → β1 | . . . | βn.

Пусть дана грамматика G. Пишем φ ⇒Gψ, сли φ = ηαθ, ψ = ηβθ и (α → β) ∈ P для некоторых слов α,

β, η, θ в алфавите N ∪ У. Если φ ⇒Gψ, то говорят, что слово ψ непосредственно выводимо из слова φ.

Когда из контекста ясно, о какой грамматике идёт речь, вместо ⇒G можно писать просто ⇒.

Пример  Пусть G = _{S}, {a, b, c}, {S → acSbcS, cS → ε}, S. Тогда cSacS ⇒GcSa.

Если ω0 ⇒G ω1 ⇒G. . . ⇒G ωn, где n _ 0, то  пишем ω0 . ⇒G   ωn и говорим, что слово ωn выводимо из слова ω0.Другими словами, бинарное отношение . ⇒G является рефлексивным,транзитивным замыканием бинарного отношения ⇒G, определённого на множестве (N ∪ У)..

При этом последовательность слов ω0, ω1,. . . , ωn называется выводом (derivation) слова ωn из слова ω0 в грамматике G. Число nназывается длиной (количеством шагов) этого вывода.

В частности, для всякого слова ω ∈ (N ∪ У).имеет место ω . ⇒G ω (так как возможен вывод длины 0).

Пример  Пусть G = _{S}, {a, b}, {S → aSa, S → b}, S              .

Тогда aSa . ⇒GaaaaSaaaa. Длина этого вывода — 3.

Язык, порождаемый грамматикой G, — это множество L(G) _ {ω ∈ У. | S . ⇒Gω}. Будем также говорить, что грамматика G порождает (generates) язык L(G).

Существенно, что в определение порождающей грамматики включены два алфавита — У и N. Это позволило нам «отсеять» часть слов, получаемых из начального символа. А именно, отбрасывается каждое слово, содержащее хотя бы один символ, не принадлежащий алфавиту У.

Пример 1.4.13. Если G = _{S}, {a, b}, {S → aSa, S → bb}, S              , то

L(G) = {anbban | n _ 0}.

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

Пример 1.4.15. Грамматика

S → abS,

S → a

и грамматика

T → aU,

U → baU,

U → ε

эквивалентны.

Классы грамматик

Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой непосредственно составляющих, НС-грамматикой, грамматикой типа 1, contextsensitive

grammar, phrase-structure grammar) называется порождающая грамматика, каждое правило которой имеет вид ηAθ → ηαθ, где A ∈ N, η ∈ (N ∪ У)., α ∈ (N ∪ У)+.

Пример. Грамматика

S → TS,

S → US,

S → b,

Tb → Ab,

A → a,

TA → AAT,

UAb → b,

UAAA → AAU

не является контекстной (последние три правила не имеют требуемого вида).

Контекстно-свободной грамматикой (бесконтекстной грамматикой, КС-грамматикой, грамматикой типа 2, context-free grammar) называется порождающая грамматика,

каждое правило которой имеет вид A → α, где A ∈ N, α ∈ (N ∪ У)..

Пример. Грамматика

S → ASTA,

S → AbA,

A → a,

bT → bb,

AT → UT,

UT → UV,

UV → TV,

TV → TA

является контекстной, но не контекстно-свободной (последние пять правил не имеют требуемого вида).

Линейной грамматикой (linear grammar) называется порождающая грамматика, каждое правило которой имеет вид A → u или A → uBv, где A ∈ N, u ∈ У., v ∈ У., B ∈ N.

Пример. Грамматика

S → TT,

T → cTT,

T → bT,

T → a

является контекстно-свободной, но не линейной (первые два правила не имеют требуемого вида).

Праволинейной грамматикой (рациональной грамматикой, right-linear grammar) называется порождающая грамматика, каждое правило которой имеет

вид A → u или A → uB, где A ∈ N, u ∈ У., B ∈ N.

Пример. Грамматика

S → aSa,

S → T,

T → bT,

T → ε

является линейной, но не праволинейной (первое правило не имеет требуемого вида).

Пример. Грамматика

S → T,

U → abba

праволинейная. Она порождает язык ..

Пример. Грамматика

S → aS,

S → bS,

S → aaaT,

S → aabaT,

S → abaaT,

S → aabbaT,

S → ababaT,

S → abbaaT,

T → aT,

T → bT,

T → ε

праволинейная.

Пример. Грамматика

S → ε,

S → aaaS,

S → abbS,

S → babS,

S → aabT,

T → abaT,

T → baaT,

T → bbbT,

T → bbaS

праволинейная.

Обобщённый вариант языка, порождаемого этой грамматикой, используется в доказательстве разрешимости арифметики Пресбургера.

Правила вида α → ε называются ε-правилами или эпсилон-правилами.

Лемма.

Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без

ε-правил является контекстной грамматикой

Язык называется языком типа 0 (контекстным языком, контекстно-свободным языком, линейным языком, праволинейным языком), если он порождается некоторой грамматикой типа 0 (соответственно контекстной грамматикой, контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебраическими языками.

Пример. Пусть дан произвольный алфавит

У = {a1, . . . , an}.

Тогда язык У. является праволинейным, так как он порождается

грамматикой

S → ε,

S → a1S,

...

S → anS.

Недетерминированные конечные автоматы.

Конечный автомат (finite automaton, finitestate machine) — это пятёрка M = ‹Q,Σ,Δ, I, F›, где Σ — конечный алфавит, Q и Δ — конечные множества,Δ c Q x Σ* x Q, I c Q c F c Q. Элементы Q называются состояниями (state), элементы I — начальными (initial) состояниями,элементы F — заключительными или допускающими (final, accepting) состояниями. Если ‹p, x, q›              c  Δc, то ‹p, x, q›              называется переходом (transition) из p в q, а слово x — меткой (label) этого перехода.

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

Каждый конечный язык является автомат­ным.

Состояние q достижимо (reachable) из состояния р, если существует путь, началом которого является р, а концом — q.

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

Пример .

Рассмотрим конечный автомат (Q, Σ, Δ,I,F), где Q = {1,2,3,4}, Σ = {а, 6, с, d}, I = {1,2,4}, F = {1,3,4}, Δ = {(1,а, 2), (1,6,4), (3, с, 4), (4,d,1)}. Удалим те состояния (и содержащие их переходы), которые не удовлетворяют требо­ваниям леммы 2.17. Получается эквивалентный конечный авто­мат (Q/,Σ,Δ/,r,F/>, где Q' = {1,4}, Δ' = {(1,6,4), (4,d,1)}, Г = {1,4} и F' = {1,4}.

Естественным обобщением конечного ав­томата является конечный преобразователь (finite-state trans­ducer), позволяющий на каждом такте отправить несколько символов в дополнительный “выходной” поток (см. [Гин, 3.3], [АхоУль, 3.1.3] или [ТраБар, 0.1, 2.1-2.6]). В некоторых кни­гах конечными автоматами называют именно такие устройства (с выходным потоком).

В данном пособии конечные преобразователи рассматривать­сяне будут.

Конфигурации конечного автомата

Конфигурацией конечного автомата на­зываетсялюбаяупорядоченная пара (q,w), где q s Q и we Σ*.

Содержательно конфигурацияпредстав­ляет собой “мгновенное описание” конечного автомата. Ес­ли представить, что исходное слово, принадлежность кото­рого рассматриваемому языку надо проверить, дано в неко­тором    “входном    потоке”,    то    в    конфигурации    (q,w)    слово w есть та часть исходного слова, котораяпока оста­лась во входном потоке (это некоторый суффикс исходно­го слова), г q — текущее состояние “управляющего устрой­ства”.

Определим на множестве всех конфигу­раций конечного автомата М бинарное отношение Ь {такт ра­боты (step)) следующим образом. Если (p,x,q) s Δ и w е Σ*, то (p,xw) Ь (q,w). Иногда вместо Ь пишут К

Бинарное отношение Ь определяется как рефлексивное, транзитивное замыкание отношения К

Лемма. Пусть дан конечный автомат М = = (Q,Σ, Δ,I,F). Слово w е Σ* принадлежит языку Ь(М) то­гда и только тогда, когда для некоторых р е I и q е F верно (p,w) Р (q,e).

Лемма. Если (q1,x) Ь (</2,е) и (Я2,у) 1~ {ч3л£), то ((/1, ху) \- ((/3, е).

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

с однобуквенными переходами

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

Пример. Рассмотрим язык, заданный конечным ав­томатом (Q, Σ, Δ, /,F), где Q = {1,2}, Σ = {а, 6, с, d}, Δ = {(1,аЬ, 2), (2,cd,1)}, I = {1,2}, F = {1,2}. Тот же язык распознаётся конечным автоматом (Q1, Σ, Δ',r,F'}, где Q' = {0,1,2,3,4,5}, Г = {0}, F' = {5}, Δ' = = {(1,а,3), (3,6,2), (2,с,4), (4Д1), (0,е,1), (0,е,2), (1,е,5), (2,е,5)}. Здесь первые два перехода заменяют старый переход (1,ab, 2} и

следующие два перехода заменяют старый переход (2, cd, 1). Что­бы обеспечить единственность начального состояния, добавлены переходы (0, е, 1} и (0, е,2). Последние два перехода в Δ' обес­печивают единственность заключительного состояния.

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

Доказательство. Согласно лемме 2.28 можно предположить, что исходный язык задан конечным автоматом (Q, Σ, Δ,I,F), не содержащим переходов с метками длины больше едини­цы, причём |/| = 1. Построим искомый конечный автомат {Q1, Σ, Δ',I1,F'), положив Q' = Q, Г = I,

Δ' = {(р,а,г) | абΣ и найдётся такое qeQ, что (?1о,г)еΔ и существует путь из р в q с меткой е},

F' = {р G Q | найдётсятакое q s F,

что существует путь из р в q с меткой е}.

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

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

Доказательство. Без ограниченияобщности можно пред­
положить, что исходный язык задан конечным автоматом
{Q, Σ, Δ,/,F), где<ЗпΣ = 0и/ = {</о}. Положим N = Q,
S = qo и Р = {р —> xq | (p,x,q) G Δ} U {р —> е | р G F}.              □

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

Доказательство. Без ограниченияобщности можно пред­
положить, что исходный язык задан праволинейной граммати­
кой, не содержащей правил вида А —> и, где и е Σ+. Поло­
жим Q = N, I = {S}, F = {A G N | (А —> е) 6 Р} и
Δ = {(Ди,В) |(А->иВ)еР}.              П

Пример. Пусть Σ = {а, 6}. Язык, порождаемый грамма­тикой S —> аа, S —> Т, Т —> ЬаТ, Т —> а, распознаётся конечным автоматом (Q, Σ, Δ, /,F), где Q = {5, Т, £}, / = {5}, F = {Е} и Δ = {(5,аа,Е>,  <S,e,T>,  (Т,Ъа,Т),  (Т,а,Е)}.

Нормальная форма праволинейных грамматик

Праволинейная грамматика в нормаль­ной форме (автоматная грамматика, регулярная граммати­ка) (finite-state grammar) — это праволинейнаяграмматика, в ко­торой каждое правило имеет вид А —> е, А —> а или А —> аВ, где A G N, В G -/V, a G Σ.

Теорема. Каждая праволинейная грамматика эквива­лентна некоторой праволинейной грамматике в нормальной форме.

Теорема. Если праволинейный язык не содержит пустого слова, то он порождается некоторой праволинейной грамматикой в нормальной форме без е-правил.

Детерминированные конечные автоматы

Конечный автомат (Q, Σ, Δ, I, F) назы­вается детерминированным (deterministic), если

1)  множество / содержит ровно один элемент,

2)  каждого перехода (p,x,q) s Δ выполняется равенство \х\ =

3) для любого символа а е Σ и для любого состояния р & Q существует не более одного состояния q е Q со свойством (р, о, 9) € Δ.

Детерминированный конечный автомат (Q, Σ, Δ,/,F) называется полным (complete), если для каждого состояния р G Q и для каждого символа абΣ найдётся такое состояние q G Q, что (р, а, </) е Δ.

Замечание. Некоторые авторы используют в определе­нии полного детерминированного конечного автомата вместо от­ношения Δ функцию S: QxΣ —> Q. От функции (5 можно перейти к отношению Δ, положив Δ = {(р, а, б(р, а)) \р & Q, в£ Σ}.

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

Доказательство. Без ограничения общности можно пред­положить, что исходный язык задан конечным автоматом (Q, Σ, Δ,/,F), содержащим только переходы с метками дли­ны единица. Длялюбых а е Σ и Н С Q обозначим Δa(Н) ^ {</ G Q | (р, а, </} G Δ для некоторого р s Д"}.

Обозначим через Р(<3) множество всех подмножеств мно­жества Q. Построим искомый полный детерминированный
конечный автомат (Q',Σ,Δ',I',F'), положив Q' = V(Q),
Δ' = {(Н,а,Δa(Н)) | Я С Q, a G Σ}, Г = {1} и
F' = {Н С Q | Н П F = 0}.             

Основные свойства автоматных языков.

Свойства замкнутости класса автоматных языков

Теорема. Класс автоматных языков замкнут относи­тельно итерации, конкатенации и объединения.

Доказательство. Без ограниченияобщности можно предпо­
ложить, что каждый из исходных языков задан конечным авто­
матом с одним начальным и одним заключительным состоянием.
Тогда во всех трёх случаях результирующий автомат получается
из исходных путём добавлениянескольких е-переходов и состо­
яний и назначения новых начальных и заключительных состоя­
ний.              □

Пример. Пусть Мх = ({1, 2,3}, Σ, Δь {1}, {2}), где Σ = {а, Ъ, с} и Δi = {(1,а,2), (2,6,3), (3, с, 1)}. То­гда язык L(Mi)* распознаётсяконечным автоматом Мг = = ({1, 2, 3, 4}, Σ, Δi U {(4, е, 1),  (2, е, 4)}, {4}, {4}).

Пример. Пусть Е = {а, 6, с}. Рассмотрим конечный автомат Mi из примера 3.2 и конечный автомат М2 = = ({4, 5},Е, Д2,{4},{5}), где Д2 = {(4, с, 4), (4, а, 5), (5, с, 5)}. Тогда язык L{M\) ■ L(M2) распознаётсяконечным автома­том Мз = ({1,2, 3,4, 5}, Е, Ai U Д2 U {(2, е, 4}}, {1}, {5}}, а язык L(Mi) U L{M2) распознаётсяконечным автоматом М^ = = ({1, 2, 3, 4, 5}, Е, Ai U Д2, {1, 4}, {2, 5}).

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

Теорема. Класс автоматных языков замкнут относи­тельно дополнения и пересечения.

Доказательство. Если язык L распознаётсяполным де­терминированным конечным автоматом (Q, Е, A,I,F), то язык Е* — L распознаётсяконечным автоматом (Q, Е, A,I,Q — F).

Пересечение выражаетсячерез объединение и дополнение
(закон де Моргана).              □

Замечание. Автоматность пересечениядвух авто­матных языков можно легко доказать и без привлече­ниятеоремы 2.43. Дляэтого достаточно построить по двум конечным автоматам с однобуквенными переходами Mi = (Qi,'E,Ai,Ii,Fi) и Мг = (Q2, Е, Д2Д2,F2) новый конеч­ный автомат М = (Qi х Q2,'E,A,Ii х l2,Fi х F2), где Д = = {{{pi,P2),a, (qi,q2)) | (pi, a, qi) G ДЬ   (р2,а, q2) € Д2}.

Лемма о разрастании для автоматных языков

Лемма (pumping lemma, лемма о разрастании, лемма о накачке, лемма-насос). Пусть L — автоматный язык над алфавитом Е. Тогда найдётся такое положительное целое число р, что для любого слова w е L длины не меньше р найдутся слова x,y,z е Е*, для которых верно xyz = w, у = е, \ху\ ^р и xylz G L для всех г ^ 0.

Доказательство. Пусть язык L распознаётсяавтоматом (Q, Е, A,I,F), содержащим только переходы с метками дли­ны единица. Положим р = \Q\. Пусть слово w является мет­кой успешного пути (<zo,ei,</i,e2,...,qn) и \w\ = п ^ р. Со­гласно принципу Дирихле найдутсятакие индексы j и к, что 0^j<k^pиqj = qk. Выберем слова х, у и z так, что \х\ = j,
\у\ = к — j и xyz = w.

Дополнительные свойства автоматных языков

Теорема. Для любого гомоморфизма h: Ef -► Щ и автоматного языка L С S* язык h(L) является автоматным.

Доказательство. Пусть исходный язык L задан конеч­
ным автоматом М = (Q, Si, A,/,F). Положим А' =
= {(p,h(x),q) | (p,x,q) G А}. Тогда язык h(L) распознаётся
конечным автоматом (Q, S2, A',I,F).

Теорема. Для любого гомоморфизма h: Щ -► Щ и ав­томатного языка L СЩ язык h^1^) является автоматным.

Доказательство. Без ограниченияобщности можно пред­
положить, что исходный язык L задан конечным автома­
том М = (Q, ХЬ, А,I,F), где А не содержит перехо­
дов с метками длины больше единицы. Положим А' =
= {(p,a,q) | a G Si и существует путь из р в q с меткой h(a)}.
Тогда язык h-1^) распознаётсяконечным автоматом М' =
= (Q, Si, А',I,F).             

Длины слов в автоматных языках

Определение.   Пусть   Д   С   N,   m   G   N   и   m   >   0.

Множество Л называется заключительно периодическим (ul­timately periodic) с периодом т, если выполнено условие (Зп0 G N)(Vn > n0)(n G Л^п + те Л).

Лемма. Пусть Л С N. Тогда равносильны следующие утверждения:

1)  множество Л является заключительно периодическим;

2)  найдутся положительное целое число т и конечные множества М С N и 1С С {0,1,..., т — 1}, такие что Л = {k G N | (к mod m) G 1С} — Л4;

3)  множество Л является объединением конечного семей­ства арифметических прогрессий.

Теорема. Язык L над однобуквенным алфавитом {а} является автоматным тогда и только тогда, когда множество {к G N | ак G L} является заключительно периодическим.

Доказательство. Длядоказательства необходимости доста­
точно рассмотреть детерминированный конечный автомат, рас­
познающий язык L.              □

Теорема. Если язык L является автоматным, то мно­жество {\w\ | w G L} является заключительно периодическим.

Доказательство. Рассмотрим конечный автомат, распознаю­
щий язык L. Заменим все символы в метках переходов на сим­
вол а. Осталось применить теорему 4.5 к полученному автомат­
ному языку над однобуквенным алфавитом {а}.

Регулярные выражения.

Определение 5.1. Регулярное выражение над алфавитом Е определяется рекурсивно следующим образом: 0 является регу­лярным выражением; 1 является регулярным выражением; если a G Е, то а является регулярным выражением; если еи/ яв­ляются регулярными выражениями, то (е+/), (е-/) и е* тоже являются регулярными выражениями.

Дляэкономии скобок будем считать, что умножение связы­вает теснее, чем сложение. Вместо e-f часто пишут просто е/.

Пример. Пусть Е = {а,Ъ}. Тогда ((а-Ь)*-(1+а)) является регулярным выражением над алфавитом Е.

Определение. Каждое регулярное выражение е над алфавитом Е задаёт (denotes, represents) некоторый язык над алфавитом Е (обозначение Ь(е)), определяемое рекурсивно следующим образом:

Ь(а) ^ {а}, если а G Е,

L(0) ^ 0,

L(l)^{e},

                               L(e+f) ^ L(e)UL(/),

L(e-f) ^ L(e) ■ L(f), L(e*) ^ L(e)*.

Заметим, что в правой части последнего выражениясимволом * обозначена итерацияязыка (см. определение 1.28).

Вместо L(e) часто пишут просто е.

Пример. Пусть Е = {а, Ъ}. Согласно определению L((ab)*-(l+a)) = {{ab)n \ п > 0} U {{ab)na \ п > 0}.

Определение. Язык L называется регулярным, если он задаётсянекоторым регулярным выражением.

Определение. Пусть е — регулярное выражение. Тогда е+ ^ е*е.

Свойства регулярных выражений.

Лемма. Регулярные выражения образуют ассоциатив­ное полукольцо с операциями (0, +, 1, •), то есть для любых регулярных выражений е, / и g выполняются следующие тож­дества:

1)  е+/ = f+e,

2)  е+0 = е,

3)  (e+f)+g = e+(f+g),

4)  е-1 = е,

5)  1-е = е,

6)  (e-f)-g = e-(f-g),

7)  e-(f+g) = e-f+e-g,

8)  (f+g)-e = f-e+g-e,

9)  e-0 = 0, 10) 0-e = 0.

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

Лемма. Для любых регулярных выражений е и / выполняются следующие тождества:

1)  е+е = е,

2)  (1+е+ее+ ... +е™-1)(е™)* = е* для любого п>\,

3)  (e*/)*e* = (е+/)*,

4)  4) 1+е(/е)*/= (е/)*.

Лемма. Для любых регулярных выражений е, / и д, если е = ef+g и е ф L(f), то е = <?/*.

Теорема Клини.

Определение. Назовём обобщённым конечным авто­матом аналог конечного автомата, где переходы помечены не словами, а регулярными выражениями. Метка пути такого ав­томата — произведение регулярных выражений на переходах данного пути. Слово w допускается обобщённым конечным ав­томатом, если оно принадлежит языку, задаваемому меткой неко­торого успешного пути.

Замечание. Каждый конечный автомат можно преоб­разовать в обобщённый конечный автомат, допускающий те же слова. Для этого достаточно заменить всюду в метках переходов пустое слово на 1, а каждое непустое слово на произведение его букв.

Замечание. Если к обобщённому конечному автомату добавить переход с меткой 0, то множество допускаемых этим автоматом слов не изменится.

Пример. Пусть Е = {а, 6, с}. Обобщённый конечный автомат (Q, Е, Д,I,F), где Q = {1,2,3}, Д = {(1,а, 2), (2,b*ba, 2), (2, Ь*,3}}, / = {1,2} и F = {3}, допускает все слова в алфавите Е, кроме слов, содержащих подслово аа.

Теорема (теорема Клини). Язык L является регуляр­ным тогда и только тогда, когда он является автоматным.

Доказательство. Пусть е — регулярное выражение. Индук­цией по построению е легко показать, что задаваемый им язык является автоматным

Обратно, пусть язык L распознаётсянекоторым (недетерми­нированным) конечным автоматом с одним начальным состоя­нием и одним заключительным состоянием. Существует эквива­лентный ему обобщённый конечный автомат (Q, Е, Д, {</i}, {42}), где (/1 ^ </2. Если есть несколько переходов с общим началом и общим концом (такие переходы называются параллельными), за­меним их на один переход, используяоперацию +.

Устраним по очереди все состояния, кроме q\ и </2. При устра­нении состояния q надо длякаждого перехода вида (pi, /1, </}, где Pi у^ q, и длякаждого перехода вида (q,f2,P2), где Р2 ^ q, до­бавить переход (pi,fig*f2,P2), где регулярное выражение д — метка перехода из q в q (если такого перехода нет, то считаем, что д = 0), и снова всюду заменить параллельные переходы на один переход, используяоперацию +.

После устранениявсех состояний, кроме q\ и </2, получится
обобщённый конечный автомат ({</i,</2}, £, A', {qi}> {42}), где
Д' = {(</ъ е1Ъ 9i); (</ъ ei2j 92)) (92j e2i, 91), (92, e22, 92)}. Очевидно,
i = L(e*iei2(e22-\-&2ie*i_ei2)*).

Синтаксические моноиды

Множества правых контекстов

Определение. Пусть L С Е* и у е Е*. Тогда множество правых контекстов слова у относительно языка L определяется так: С^ (у) ^ {г е Е* | yz G L}.

Пример. Пусть Е = {а, 6} и L = {anban \ п ^ 0}. Тогда

1)   С{1\а1) = {akbak+i \ к > 0},

2)  если г ^ j, то С^ (a*baJ) = {a*~J},

3)  если i < j, то СL {d^ba1) = 0,

4)  если |г/|ь > 1, то С^ (у) = 0.

Лемма. Если язык L распознаётся полным де­терминированным конечным автоматом (Q, Е, Д,I,F), то \{С{1\у) \у GE*}| < \Q\.

Доказательство.   Пусть   /   =    {s}.   Введём   обозначение

(г)

J ^ {CL (у) | у G Е*}. Определим функцию /: J —> Q, положив /(А) равным Aj,(s), где у — некоторое слово, для которого вы­полнено условие С^ (у) = А (если существует несколько таких слов у, то можно использовать, например, первое среди них в лексикографическом порядке).

Заметим, что для любых слов и и v, если С^г (и) 7^ С^г (v),
то A„(s) у^ Av(s). Следовательно, функция / является инъек-
тивной.

Лемма. Если L С Е* и множество {С^г)(у) | у е Е*} конечно, то язык L является автоматным.

Доказательство. Язык L распознаётсяполным детерми­
нированным конечным автоматом (Q, Е, Д, /,F), где Q =
= {С^ (у) | у G Е*}, / = {С^ (е)}, F = {CL (у) \ у G L},
Д = {(С«(у),а,С«(уа))|у€Е*, а G Е}.

Теорема. Язык L С E* является автоматным тогда и только тогда, когда множество {С^г)(у) | у е Е*} конечно.