Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3 Архитектура Биология География Другое Иностранные языки Информатика История Культура Литература Математика Медицина Механика Образование Охрана труда Педагогика Политика Право Программирование Психология Религия Социология Спорт Строительство Физика Философия Финансы Химия Экология Экономика Электроника

1 Автоматы с магазинной памятью (стековый автомат). Конфигурация. Языки распознаваемые автоматом с магазинной памят

1 Автоматы с магазинной памятью (стековый автомат). Конфигурация. Языки распознаваемые автоматом с магазинной памят

Автомат с магазинной памятью (МП-автомат, магазинный автомат, стековый автомат) (pushdown automaton) — это шестёрка M = <Q, Σ, Γ, Δ,I,F>, где Q, Σ, Γ и Δ —конечные множества, I ⊆ Q, F ⊆ Q и Δ ⊆ (Q × × ) × (Q × ). Здесь Q — множество состояний, Σ — входной алфавит, Γ — алфавит магазинной памяти (stack alphabet), Δ — множество переходов (transition relation), элементы I называются начальными состояниями, элементы F — заключительными или допускающими состояниями. Пример. Пусть Q = { 1, 2}, Σ= { a, b}, Γ= { A, B}, Δ= {<<1,a,ε>, <1,A>>, <<1,b,ε>, <1,B>>, <<1,ε,ε>, <2,ε>>, <<2,a,A>, <2,ε>>, <<2,b,B>, <2,ε>>}. I = { 1}, F = { 2}.Тогда <Q, Σ, Γ, Δ,I,F> —МП-автомат. Конфигурацией МП-автомата называетcя любая тройка <q, w, α>, где q ∈ Q, w ∈ , α ∈ . Язык, распознаваемый МП-автоматом, — множество всех слов, допускаемых этим МП-автоматом. Язык, распознаваемый МП-автоматом M, обозначается L(M). Пример. Пусть M — МП-автомат из предыдущего примера. Тогда L(M)= { | u ∈ }.

2 Автомвты с магазинной памятью с однобуквенными переходами.

Теорема. Каждый МП-автомат эквивалентен некоторому МП-автомату <Q, Σ, Γ, Δ,I,F >,где |Q| =2 и каждый переход <<p, x, β>,<q, γ>> ∈ Δ удовлетворяет требованиям |x| =1, |β| ≤1 и |γ| ≤ 2. Доказательство. Пусть исходным МП-автоматом распознаётся контекстно-свободный язык L ⊆ Σ∗. Язык L −{ ε} порождается некоторой контекстно-свободной грамматикой <N,Σ,P,S>, в которой каждое правило имеет вид A → aγ,где A ∈ N, a ∈ Σ, γ ∈ и |γ| ≤ 2. Положим Γ= N, Q = { 1, 2}, I = { 1}, Δ= {<<2,a,A>,<2,γ>> | (A→ aγ)∈ P }∪{ <<1,a,ε>,<2,γ>> | (S → aγ)∈ P },F = { 1, 2}, если ε ∈ L, { 2}, если не ∈ L. Теорема. Каждый МП-автомат эквивалентен некоторому МП-автомату <Q, Σ, Γ, Δ,I,F >, в котором каждый переход <<p, x, β>,<q, γ>> ∈ Δ удовлетворяет требованиям |x| =1, |β| ≤ 1 и |γ| 1. Доказательство. Пусть исходным МП-автоматом распознаётся контекстно-свободный язык L ⊆ . Язык L −{ ε} порождается некоторой контекстно-свободной грамматикой G = <N, Σ,P,S>, в которой каждое правило имеет один из следующих трёх видов: A → a, A → aB, A → aBC,где A ∈ N, B ∈ N, C ∈ N, a ∈ Σ. Легко добиться того, чтобы B ≠ S и C ≠S в правилах грамматики G. Положим Q = N ∪{⊥},где ⊥ не ∈ N. Далее, положим Γ= N, I = { S},F = { S, ⊥}, если ε ∈ L, {⊥}, если не ∈ L. Δ= {<<A, a, ε>, <B, C>> | (A → aBC) ∈ P }∪ {<<A, a, ε>, <B, ε>> | (A → aB) ∈ P }∪ {<<A, a, D>, <D, ε>> | (A → a) ∈ P, D ∈ N }∪{<<A, a, ε>, <⊥,ε>> | (A → a) ∈ P }.

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

Теорема: Язык регулярен тогда и только тогда, когда он распознается конечным автоматом. Д-во: (если язык регулярен, то он принадлежит замыканию класса, содержащего однобуквенные языки и пустое мн-во, от-но объединения, конкатенации и звездочки Клини). Пусть имеется конечный автомат M=(K,∑,∆,s,F). Мы должны построить регулярное выражение R такое, что L(R)=L(M). Представим L(M) в виде объединения конечного числа более простых языков. Пусть K={q1….qn}, и s=q1. Для i,j=1,…,n и k=0,…,n будем определять R(i,j,k) как мн-во всех слов ∑*, которые могут перевести М из состояния qi в состояние qj без прохождения через промежуточное состояние с номером k+1 или более (конечные точки qi и qj могут иметь номера больше чем k). Когда k=n, мы получаем, что R(i,j,n)={ωÎ∑*|<q,ω> |-*M<qj,e>}. Следовательно L(M)=U{R(1,j,n)|qiÎF}. Значит, если все мн-ва R(i,j,k) окажутся регулярными, то регулярным будет и L(M). То, что R(i,j,k) – регулярно, доказывается по индукции k. Для k=0 возможны 2случая: 1. если i≠j, то R(i,j,0)={aÎ∑U{e}|<qi,a,qj>Î∆}. 2. если i=j, то R(i,j,0)={e}U{aÎ∑U{e}|<qi,a,qj>Î∆}. Каждое из этих мн-в является конечным, а следовательно регулярным. Теперь предположим, что для всех i,j уже доказано, что R(i,j,k-1)-регулярные языки. Тогда R(i,j,k)= R(i,j,k-1)U R(i,k,k-1)R(k,k,k-1)* R(k,j,k-1). Данное равенство означает, что при движении из qi в qj без прохождения через состояния с номерами, большими чем k, у автомата М есть 2варианта: 1. идти из qi в qj через состояния с номерами, большими чем k-1; 2. идти из qi в qk, затем из qk в qk 0 или более раз, затем идти из qk в qj; каждый раз без прохождения через промежуточные состояния с номерами, большими k-1. Таким образом, язык R(i,j,k) регулярен при любых i,j,k. Значит, регулярным является и язык L(M). Теорема доказана, док-во и является алгоритмом нахождения регулярного выражения для языка распознаваемого детерминированным конечным автоматом.

4 Деление контекстно-свободных языков.

Теорема. Пусть — контекстно-свободный язык над алфавитом Σ и — автоматный язык над алфавитом Σ. Тогда язык { x ∈ | (∃y ∈ ) xy ∈ } является контекстно-свободным. Доказательство. Пусть < , Σ, , , > —МП-автомат, распознающий язык Без ограничения общности можно считать, что для каждого перехода <<p, x, β>, <q, γ>> ∈ выполняется неравенство |x|≤ 1. Пусть < , Σ, , , > — конечный автомат, распознающий язык . Без ограничения общности можно считать, что ∩ ( × )= ∅ и длякаждого перехода <p, x, q> ∈ выполняется равенство |x| =1. Тогда язык { x ∈ | (∃y ∈ ) xy ∈ } распознаётся МП-автоматом <Q, Σ, , Δ,I,F>,где Q = ∪ ( × ), I = , F = × и Δ= ∪ {<<p, ε, ε>, << , >,ε>> | ∈ , ∈ }∪ {<<< , >,ε,β>, << , >,γ>> | << ,a,β>, < ,γ>> ∈ , < ,a, > ∈ , для некоторого a ∈ Σ}∪{<<< , >,ε,β>,<< , >,γ>>| << ,ε,β>,< ,γ>> ∈ , ∈ }. Упражнение. Существует ли такой контекстно-свободный язык L ⊆ ,чтоязык Subw(L) = { | — подслово некоторого слова из L} не является контекстно-свободным? Ответ. Нет. Положив в теореме = L и = ,получим, что множество всех префиксов слов из языка L являетcя контекстно-свободным. То же верно для множества суффиксов.

5 Детерминированный конечный автомат. Языки распознаваемые детерминированным автоматом. Примеры.

Конечный автомат-это пятёркаM=(K, Σ, δ,s,F), где Σ -алфавит, K- конеч. набор состояний, s - начальное состояние, F- конеч. сост. δ -переход. Каждый конечный язык является автоматным. Конечный автомат (K, Σ, δ,s,F) называется детерминированным, если 1)мн-во s содержит ровно один элемент, 2) для каждого перехода (p, x, q)∈ δ выполняется равенство |x| = 1; 3) для любого символа a ∈ Σ и для любого сост p ∈ Q существует не более 1го сост q ∈ Q со св-вом (p, a, q)∈ Δ. Пример: Пусть M детерминированный конечный автомат <K, Σ, δ, s, F>, где:K = {q0, q1}, Σ = {a, b}, s = q0, F = {q0}, а δ это функция, заданная следующей таблицей:

q |σ|δ(q, σ)

q0 |a| q0

q0| b| q1

q1| a| q1

q1| b| q0

Язык, распознаваемый конечным автоматом M, — это я зык L (M), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Замечание. Если I ∩ F , то я зык, распознаваемый конечным автоматом <Q, Σ, δ, I, F>, содержит ε. Пример. Пусть M = <Q, Σ, δ, I, F>, где Q = { 1, 2 }, Σ = {a, b}, δ = {< 1, a, 2 >, < 2, b, 1> }, I = { 1 } и F = { 1, 2 }. Тогда L (M) = { (ab) ⁿ | n ≥ 0 } ∪ { (ab) ⁿa | n ≥ 0 }.

6 Инварианты контекстно-свободных языков.

Инвариант или инвариантность — термин, обозначающий нечто неизменяемое. Теорема. Каждый контекстно-свободный язык над однобуквенным алфавитом является автоматным. Доказательство. Пусть дан контекстно-свободный язык L над алфавитом { a}. Согласно лемме о разрастании [(: Пусть L — контекстно-свободный язык над алфавитом Σ. Тогда найдётся такое натуральное число p, что для любого слова ω ∈ L длины не меньше p найдутся слова u, v, x, y, z ∈ Σ^∗ , для которых верно uvxyz = ω, vy ≠ ε (то есть v ≠ ε или y ≠ ε), |vxy| <= p и uvⁱxyⁱz ∈ L для всех i ∈ N.)] найдётся такое натуральное число p, что множество { k ∈ N | a^k ∈ L} является объединением некоторого семейства арифметических прогрессий, причём у каждой прогрессии первый член и шаг не больше числа p. Так как существует лишь конечное число прогрессий натуральных чисел с таким ограничением, то рассматриваемое семейство конечно. Следовательно, язык L является автоматным.

7 Классы грамматик. Понятие контекстно-свободная граматика (CFG).

Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Для отнесения грамматики к тому или иному типу необходимо соответствие всех её правил (продукций) некоторым схемам. По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу): тип 0. неограниченные грамматики — возможны любые правила; тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом»; сам нетерминал заменяется непустой последовательностью символов в правой части; тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала; тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.

Контекстно-свободная грамматика — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что возможность применить продукцию к нетерминалу, в отличие от общего случая неограниченной грамматики Хомского, не зависит от контекста этого нетерминала. Например: Слово с переворотом (Палиндром). Задаётся формулой ; Терминалы: буквы алфавита Σ; Нетерминал: S; Продукции: ; Начальный нетерминал — S.

8 Конечные автоматы и регулярные выражения.

Конечный автомат — это пятёрка M = < K, Σ, , s, F >, гдеK – конечный набор состояний, Σ — конечный алфавит, s – начальное состояние, F – множество конечных состояний, — функция перехода, функция из K xΣ. Если язык регулярен, то он принадлежит замыканию класса, содержащего однобуквенные языки и , относительно , конкатенации и звездочки Клини. Язык регулярен тогда и только тогда, когда он распознается конечным автоматом. Пусть имеется конечный автомат M = <K, Σ, ∆, s, F>. Построим регулярное выражение R такое, что L(R) = L(M). Представим L(M) в виде объединения конечного числа более простых языков. Пусть K = {q1,…, qn}, и s = q1. Для i, j = 1,…, n и k = 0,…, n будем определять R(i, j, k) как множество всех слов Σ∗, которые могут перевести M из состояния qi в состояние qj без прохождения через промежуточное состояние с номером k + 1 или больше (конечные точки qi и qj могут иметь номера большие чем k). Когда k = n, мы получаем, что R(i, j, n) = {w ∈ Σ∗|<q, w> |-∗M <qj, e>}. Следовательно L(M) = {R(1, j, n)|qj ∈ F}. Значит, если все множества R(i, j, k) окажутся регулярными, то регулярным будет и L(M). То, что каждое R(i, j, k) -регулярно, доказывается индукцией по k. Для k = 0 возможны два случая. Если i j, то R(i, j, 0) = {a ∈ Σ ∪ {e}|<qi, a, qj> ∈ ∆}. Если i = j, то R(i, j, 0) = {e}∪{a ∈ Σ∪{e}|<qi, a, qj> ∈ ∆}. Каждое из этих множеств является конечным, а следовательно регулярным. Теперь предположим, что для всех i, j уже доказано, что R(i, j, k − 1) регулярные языки. Тогда R(i, j, k) = R(i, j, k − 1) ∪ R(i, k, k − 1)R(k, k, k − 1)∗R(k, j, k − 1). Данное равенство означает, что при движении из qi в qj без прохождения через состояния с номерами, большими чем k, у автомата M есть два варианта: 1. идти из qi в qj без прохождения через состояния с номерами, большими чем k − 1; 2. идти из qi в qk, затем из qk в qk 0 или более раз, затем идти из qk в qj; каждый раз без прохождения через промежуточные состояния с номерами, большими чем k − 1. Таким образом язык R(i, j, k) регулярен при любых i, j, k. Значит, регулярным является и язык L(M).

9 Конечные автоматы. Детерминированный конечный автомат. Конфигурация.

Конечный автомат-M=(K, Σ, Δ,s,F), где Σ -алфавит, K- конеч. набор состояний, s - начальное состояние, F- конеч. сост. Δ-переход. Каждый конечный язык является автоматным. Конечный автомат (K, Σ, Δ,s,F) называется детерминированным, если 1)мн-во s содержит ровно один элемент, 2) для каждого перехода (p, x, q)∈ Δ выполняется равенство |x| = 1; 3) для любого символа a ∈ Σ и для любого сост p ∈ Q существует не более 1го сост q ∈ Q со св-вом (p, a, q)∈ Δ. ДКА (K, Σ, Δ,s,F) называется полным, если для каждого состояния p ∈ Q и для каждого символа a ∈ Σ найдётся такое состояние q ∈ Q, что (p, a, q)∈ Δ. Конфигурацией конечного автомата называется любая упорядоченная пара (q, w), где q ∈ Q и w ∈ Σ∗. Конфигурация представляет “мгновенное описание” конечного автомата. Если представить, что исходное слово, принадлежность которого рассматриваемому языку надо проверить, дано в некотором “входном потоке”, то в конфигурации (q, w) слово w есть та часть исходного слова, которая пока осталась во входном потоке, а q — текущее состояние “управляющего устройства”.

10 Конечные представления языков. Регулярные выражения и регулярные языки.

Σ={0,1} 0,1,u, ◦,*,{,},".", ",". независимо от того сколь мощные методы будем использовать для представления языков все равно конечными выражениями можно представить не более счетного кол-во языков.

пусть у нас есть алфавит Σ. Тогда 1)∅ и каждый символ алфавита Σ являются регулярными выражениями.2)Если α и β-регулярные выражения, то (αβ)-тоже регулярное выражение. 3)Если α и β регулярные выражения, то (α ∪ β) тоже регулярное выражение. 4)Если α регулярное выражение, то α^∗ регулярное выражение. 5)Других регулярных выражений нет.

Регулярными языками- наз. языки, которые могут быть описаны с помощью регулярных выражений.

с помощью регулярных выражений нельзя описать некоторые языки, которые очень просто описываются другими способами. К примеру, язык {0n1n|n ≥ 0} НЕ может быть описан регулярным выражением. в общем случае регулярные выражения не могут быть хорошим методом.

11 Лемма о расрастании (pumping lemma) контекстно-свободных грамматик.

Если L — КС-язык над алфавитом V, то . Иначе говоря, любую достаточно длинную цепочку в КС-языке можно разбить на пять частей так, что повторение второй и четвертой частей произвольное количество раз (возможно, 0) не приведут к выходу за пределы языка. Доказательство. Пусть задан КС-язык (V, N, S, G), причем грамматика языка приведена (т.е. не содержит правил вида A → ε или A → B). Поскольку количество нетерминальных символов конечно, равно как и длина каждого правила вывода, то длина цепочки, высота дерева вывода для которой не превышает |N|, также ограничена сверху неким числом n. Рассмотрим цепочку . В силу вышесказанного высота дерева ее вывода превысит |N|, т.е. найдется путь из аксиомы в один из терминальных символов, длина которого будет больше, чем количество нетерминальных символов грамматики. Поскольку на каждом шаге заменяется один нетерминальный символ, как минимум один нетерминальный символ Q на этом пути будет заменён дважды. Из этого следует, что существует цепочка xQy с непустыми x или y, выводящаяся из Q. Следовательно, в процессе вывода S →* α процесс вывода Q →* xQy можно повторять сколь угодно много раз или опустить. Тривиальное следствие: в любом бесконечном КС-языке найдется бесконечное подмножество цепочек, длины которых образуют возрастающую арифметическую прогрессию.

12 Метод перевода контекстно-свободных грамматик (CFG) на автоматы со стеком.

Конструктивный алгоритм построения PDA по CFG: Для данной CFG G строится PDA, имитирующий левосторонний вывод для G. Пусть G = (V, T, Q, S). Строится PDA P, который распознает язык L (G) по пустому стеку: P = ({ q}, T, V ∪ T, δ, q, S), где функция переходов δ определена следующим образом: для каждой переменной A, δ (q, ε, A) = { (q, β) | A → β правило вывода в G }; для каждого терминала a, δ (q, a, a) = { (q, ε)}. I → a | b | Ia | Ib | I0 | I1. E → I | E ∗ E | E + E | (E). PDA P = ({q}, T, Γ, δ, q, S): T = { a, b, 0, 1, (,), +, ∗}. Γ = T ∪ {I, E }. δ: δ (q, ε, I) = { (q, a), (q, b), (q, Ia), (q, Ib), (q, I0), (q, I1)}. δ (q, ε, E) = { (q, I), (q, E + E), (q, E ∗ E), (q, (E))}. δ (q, a, a) = { (q, ε)}; δ (q, b, b) = {(q, ε)}; δ (q, 0, 0) = { (q, ε)}; δ (q, 1, 1) = { (q, ε)}; δ (q, (, () = { (q, ε)}; δ (q,),)) = {(q, ε)}; δ (q, +, +) = {(q, ε)}; δ (q, ∗, ∗) = { (q, ε)}.

13 Минимизация числа состоянии для конечных автоматов. Примеры.

Существует быстрый алгоритм, позволяющий по произвольному детерминированному конечному автомату находить минимальный (по количеству состояний автомат среди детерминированных конечных автоматов, эквивалентных исходному автомату. Доказательство. Без ограничения общности можно предположить, что дан полный детерминированный конечный автомат <Q,Σ,Δ, I, F>, все состояния которого достижимы из начального состояния(для обеспечения полноты достаточно добавить одно состояние). Для каждого натурального числа i определим на множестве Q отношение эквивалентности ≡ _i: p ≡₀ q ⇐⇒ (p ∈ F и q ∈ F) или (p∉ F и q ∉ F), p ≡_i+1 q ⇐⇒ p ≡_i q и Δ_a(p) ≡_i Δ_a(q) для каждого a ∈ Σ. Легко видеть, что p ≡_i q тогда и только тогда, когда никакое слово длины не больше i не различает p и q. Обозначим n = |Q|. Легко проверить, что для любого k ≥ n отношение ≡_k совпадает с отношением ≡_n−1. Используя классы эквивалентности отношения ≡_n−1 как состояния, можно построить минимальный полный детерминированный конечный автомат. Удалив из него бесполезное состояние (из которого не достижимо ни одно заключительное состояние), если такое имеется, получим искомый минимальный детерминированный конечный автомат. Пример. Рассмотрим полный детерминированный конечный автомат <{1,2, 3, 4, 5, 6},{a, b},Δ, {1},{1,3}>, где Δ = {<1, a, 2>, <2, b, 3>, <3, a, 4>, <4, b, 1>,<4, a, 5>,<5, a, 5>,<1, b, 6>, <2, a, 6>, <3, b, 6>,<5, b, 6>, <6, a, 6>, <6, b, 6>}. Он эквивалентен минимальному детерминированному конечному автомату <{{1, 3}, {2, 4}}, {a, b},Δ’, {{1, 3}}, {{1, 3}}>, где Δ’ = {<{1, 3}, a, {2, 4}>, <{2, 4}, b, {1, 3}>}.

14 Недтерминированный конечный автомат. Языки распознаваемые недетерминированным автоматом.

Конечный автомат-это пятёркаM=(K, Σ, δ,s,F), где Σ -алфавит, K- конеч. набор состояний, s - начальное состояние, F- конеч. сост. δ -переход. Каждый конечный язык является автоматным. Конечный автомат (K, Σ, δ,s,F) называется детерминированным, если 1)мн-во s содержит ровно один элемент, 2) для каждого перехода (p, x, q)∈ δ выполняется равенство |x| = 1; 3) для любого символа a ∈ Σ и для любого сост p ∈ Q существует не более 1го сост q ∈ Q со св-вом (p, a, q)∈ Δ. Пример: Пусть M детерминированный конечный автомат <K, Σ, δ, s, F>, где:K = {q0, q1}, Σ = {a, b}, s = q0, F = {q0}, а δ это функция, заданная следующей таблицей:

q |σ|δ(q, σ)

q0 |a| q0

q0| b| q1

q1| a| q1

q1| b| q0

Язык, распознаваемый конечным автоматом M, — это я зык L (M), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Замечание. Если I ∩ F , то я зык, распознаваемый конечным автоматом <Q, Σ, δ, I, F>, содержит ε. Пример. Пусть M = <Q, Σ, δ, I, F>, где Q = { 1, 2 }, Σ = {a, b}, δ = {< 1, a, 2 >, < 2, b, 1> }, I = { 1 } и F = { 1, 2 }. Тогда L (M) = { (ab) ⁿ | n ≥ 0 } ∪ { (ab) ⁿa | n ≥ 0 }.

15 Операции над множествами. Функций и отношения. Перечислимые и не перечислимые множества.

Объединение: A ∪ B = {x|x ∈ A или x ∈ B}; объединения семейства мн-в: А_i (i ∈ I) ∪A_i={x| _i0 ∈ I, x ∈ A_io};

Пересечение: A ∩ B = {x|x ∈ A и x ∈ B};Пересечение семейства мн-в A: ∩_i∊A A_i {x|x ∈ A, для всех i ∈ I};

Разность: A \ B = {x|x ∈ A и x ∉ B}; Дополнение: Ā = U\A {x|x ∈ U и x∉A }; симметричная разность: A ∆ B=(А\B) ∪(B/A)=(A∪B)\(A∩B).

1) Декартовым произведением мн-в A и А_n наз. мн-вом A₁×A₂×...×A_n={<a₁₁,...,a_n>|a₁ ∈ A₁,..., a_n∈A_n}

2) Бинарным отношением на мн-вах A и B называется подмн-во A × B. К примеру, {(1, b), (1, c), (3, d), (9, d)} является бинарным отношением на наборах {1, 3, 9} и {b, c, d}, а {(i, j)|i, j ∈ N и i < j} это отношение "меньше", задано оно на N × N.

a) dom_r ={x| _y, (x,y) ∈R}; б)ran_r ={x| _y, (y,x)∈R }; в)(-R) Ṝ=(A×B)\R; г)R^-1={(x,y)| (y,x) ∈R}; д)R(x)={y| x∈X, (x,y) ∈R};е)R₁⊆A×B и R₂⊆B×C R₁◦R₂={(x,y)| _z, (x,z) ∈R₁ и (z,y) ∈R₂};

отношение f наз ф-я из А в B, если dom_f =A и ran_f ⊆B и для всех x,y₁,y₂. из (x,y₁) ∈f и (x,y₂) ∈f=>y₁=y_2.

Функция f: A → B наз. инъективной, если для любого b∈B сущ-ет не более 1го a∈A, f(a)=b.

Функция f: A → B наз. сюръективной (отображение на), если ran(f)=B.

Функция наз. биективной (взаимно-однозначная), если f и сюръективна и инъективна.

если f⊆A ×B и g⊆B×C ф-я, то их композиция f◦g⊆A×C, f◦g является функцией.

если f-биективная ф-я, то обратная ф-я f ^-1 определяется как обратное отн-е.

16 Основные виды бинарных отношений. Рефлексвное и транзитивное замыкание.

Бинарное отношение R ⊆ A × A называется:1)рефлексивным, если (a, a) ∈ R для каждого элемента a ∈ A; 2) иррефлексивным (а,а) ∉ R; 3)симметричным, если из того, что (a, b) ∈ R => (b, a) ∈ R для любых элементов a, b ∈ A; 4)антисимметричным (a, b) ∈ R => (b, a) ∈ R => a=b; 5)транзитивным (a, b) ∈ R и (b, c) ∈ R => (a, c) ∈ R для любых эл.a, b, c ∈ A.

Отношение, которое одновременно является рефлексивным, симметричным и транзитивным, называется отношением эквивалентности. R [a]R = {b|(a, b) ∈ R}. Бинарным отношением на мн-ве А наз: 1)предпорядком-если рефлексивно и транзитивно; 2)частичный порядок - рефлексивно, антисимметрично и транзитивно. -частичный порядок наз: линейный - у х для всех х,у ∈ А. мн-во А задано с частичным порядком , тогда А наз. частично упорядоченное мн-во. эл. а частично упорядоченное мн-ва А наз максим(мин), если из того что а х (х а) следует а=х. эл. а из А наз наибольшим(наимен) если х а(а х) для всех х∈А.

17 Пересечение и дополнение контекстно-свободных языков.

Теорема. Неверно, что для любых контекстно-свободных языков L₁ и L₂ язык L₁ ∩ L₂ тоже контекстно-свободный. Доказательство. Положим L1 = { a^mb^mcⁿ | m >= 0,n >= 0}и L2 = { a^mbⁿcⁿ | m >= 0,n >= 0}. Рассмотрим язык L = { aⁿbⁿcⁿ | n 0} над алфавитом { a, b, c}. Утверждение леммы: Пусть L — контекстно-свободныйязык над алфавитом Σ. Тогда найдётся такое натуральное число p, что для любого слова ω ∈ L длины не меньше p найдутся слова u, v, x, y, z ∈ Σ∗, для которых верно uvxyz = ω, vy ≠ ε (то есть v ≠ ε или y ≠ ε), |vxy| <= p и uvⁱxyⁱz ∈ L длявсех i ∈ N. не выполняется ни для какого натурального числа p. Действительно, если uvxyz = a^pb^pc^p, |vy| > 0 и |vxy| <= p, то |vy|_a =0 или |vy|_c =0. Следовательно, |uvvxyyz|_a = p или |uvvxyyz|_c = p. Так как |uvvxyyz| > 3p,то uvvxyyz не ∈ L. Из этого можно заключить, что язык L не является контекстно-свободным. отсуда было доказано, что язык L1 ∩ L2 не является контекстно-свободным.

Теорема. Неверно, что для любого контекстно-свободного языка L ⊆ Σ^∗ язык Σ^∗ − L тоже контекстно-свободный. Доказательство. Положим L =Σ^∗ −{ aⁿbⁿcⁿ | n >=0},гдеΣ= { a, b, c}. Рассмотрим алфавит Σ= { a, b, c}.Язык L =Σ^∗ −{ aⁿbⁿcⁿ | n >=0} является линейным, поскольку L = L₁ ∪ L₂ ∪ (Σ^∗ − L₃), где языки L₁ = { a^mbⁿc^k | m ≠ n, k >= 0}и L₂ = { a^mbⁿc^k | n ≠ k, m >= 0} являются линейными, а язык L₃ = { a^mbⁿc^k | m >= 0,n >= 0,k >= 0} является автоматным и можно применить теорему 1:Каждый автоматный язык является право-линейным; и теоремму 2: Если L1 и L2 — линейные языки над алфавитом Σ,то L1 ∪ L2 тоже линейный язык. следовательно было доказано, что язык L является линейным (и следовательно, контекстно-свободным).

18 Пересечение контекстно-свободного языка с автоматным языком.

Теорема. Если L₁ — контекстно-свободный язык и L₂ —автоматный язык, то язык L₁ ∩ L₂ является контекстно-свободным. Доказательство. Пусть <N, Σ,P,S> — контекстно-свободная грамматика, порождающая язык L₁. Без ограничения общности можно считать, что множество P содержит только правила вида A → a и A → α, где A ∈ N, a ∈ Σ и α ∈ N^∗. Пусть <Q, Σ, Δ,I,F> —конечный автомат, распознающий язык L₂. Без ограничения общности можно считать, что для каждого перехода <p, x, q> ∈ Δ выполняется равенство |x| =1. Построим контекстно-свободную грамматику < , , , >, порождающую язык L₁ ∩ L₂.Положим = { }∪ (Q × N × Q), P = { S →<p, S, q>| p ∈ I, q ∈ F }∪{<p, A, q>→ a |<p, a, q >∈ Δ, (A → a) ∈ P }∪{<p₀,A,p_n>→<p₀,B₁,p₁>... <p_{n− 1},B_n,p_n>|(A → B₁...B_n) ∈ P, p₀ ∈ Q,...,p_n ∈ Q}, где — новый символ (не принадлежащий множеству Q× N × Q).

19 Понятие языка и алфавита, операции над языками.

Алфавит-конечный (непустой) набор символов. пример, бинарный алфавит {0, 1}. Словом называется конечная последовательность символов алфавита. пустое слово - e, Слова - u,v,x,y,z,w. Множество всех слов алфавита Σ, будет обозначаться Σ^∗. Длиной слова является его длина как последовательности символов. (w через|w|, пример |101|=3, |e|=0). функция: w: {1,..., |w|} → Σ, при этом w(j) при 1 ≤ j ≤ |w| это j-й символ слова w. Конкатенация слов x и y, обозначаемая как x ◦ y или просто xy, это слово x, за которым записано слово y. |w| = |x| + |y|, w(j) = x(j) для j = 1,..., |x| и w(|x| + j) = y(j) для j = 1,..., |y|. w ◦ e = e ◦ w = w. СловоV называется подсловом слова w в том, и только в том случае, если существуют слова x и y такие, что w = xVy. Обращением слова w, записываемым как wR, будем называть то же самое слово, записанное наоборот. Формальное определение такого:

1)Если w -слово|w|=0, то w^R = w = e. 2)Если |w|=n+1>0, то w = ua, a ∈ Σ, и w^R = au^R.

Любое множество слов алфавита Σ, то есть любое подмножество Σ∗, мы будем называть языком.

Σ^*-счетное, для всех Σ -конечное мн-во.

1)Для каждого k ≥ 0 все слова длины k перечисляются решения всех строк длины k + 1. 2)Все n^k слов длины k перечисляются в лексикографическом порядке. операция над языками:1) А-язык, то Ā= Σ^*\А; 2) конкатенация языков L₁ и L₂ -языки алфавита Σ, то L= L₁ ◦ L₂ L = {w ∈ Σ^∗|w = x ◦ y, x ∈ L₁, y ∈ L₂}. 3) навешивание звездочки Клини на язык L, L^∗. L^∗ -это мн-во всех слов, получаемых путем конкатенации нуля или более слов из L (конкатенация нуля -это e, а конкатенация одного слова -это само это слово). L^∗ = {w ∈ Σ^∗|w = w₁ ◦...◦ w_k, k ≥ 0 и w₁,..., w_k∈ L}.

20 Порождающая грамматики. Эквивалентность грамматики.

Порождающей грамматикой (грамматикой типа 0) называется четвёрка G <N,Σ, P, S>, где N и Σ — конечные алфавиты, N∩Σ = ∅, P⊂(N∪Σ)⁺×(N∪Σ)^∗, P конечно и S ∈ N. Здесь Σ — основной алфавит (терминальный алфавит), его элементы называются терминальными символами или терминалами, N — вспомогательный алфавит (нетерминальный алфавит), его элементы называются нетерминальными символами, нетерминалами или переменными, S — начальный символ (аксиома). Пары (α, β) ∈ P называются правилами подстановки, просто правилами или продукциями и записываются в виде α → β. Пример. Пусть даны множества N = {S}, Σ = {a, b, c}, P = {S → acSbcS, cS → ε}. Тогда < N, Σ ,P,S> - является порождающей грамматикой. Две грамматики эквивалентны, если они порождают один и тот же язык. Пример. Грамматика S → abS, S → a и грамматика T → aU, U → baU, U → ε эквивалентны.

21 Свойсва контекстно-свободных языков (CFL). Примеры. Теорема о контекстно-свободном языке.

CFL – замкнуты относительно следующих операций: объединения, конкатенации, замыкания, обращения. Теорема 1. Если L — контекстно-свободный язык, то L^∗ тоже контекстно-свободный язык. Доказательство. Пусть язык L порождается грамматикой <N, Σ,P,S>. Тогда язык L^∗ порождается грамматикой <N∪{T}, Σ,P ∪{ T → ST, T → ε},T >,где T не ∈ N ∪ Σ. Теорема 2. Если L₁ и L₂ — контекстно-свободные языки над алфавитом Σ,то L₁ · L₂ тоже контекстно-свободный язык. Доказательство. Пусть язык L₁ порождается грамматикой <N₁, Σ,P₁,S₁> и L₂ порождается грамматикой <N₂, Σ,P₂,S₂>, где N₁ ∩ N₂ = ∅.Тогда L₁ · L₂ порождается грамматикой <N₁∪ N₂∪{ T }, Σ,P₁∪ P₂∪{ T → S₁S₂},T >,где T не ∈ N₁∪ N₂∪ Σ. Теорема 3. Если L₁ и L₂ — контекстно-свободные языки над алфавитом Σ,то L₁ ∪ L₂ тоже контекстно-свободный язык. Доказательство. Пусть язык L₁ порождается грамматикой <N₁, Σ,P₁,S₁> и L₂ порождается грамматикой <N₂, Σ,P₂,S₂>, где N₁ ∩ N₂ = ∅.Тогда L₁ ∪ L₂ порождается грамматикой <N₁ ∪ N₂ ∪{ T }, Σ,P₁ ∪ P₂ ∪{ T → S₁,T → S₂},T >,где T не ∈ N₁ ∪ N₂ ∪ Σ. Теорема 4. Если L — контекстно-свободный язык, то L^R тоже контекстно-свободный язык. Множество CFL не замкнуто относительно операции пересечения. Пример: L­₁={0­ⁿ1ⁿ2^i­ | n≥1,i≥1}, L­₂={0­ⁱ1ⁿ2^i­ | n≥1,i≥1}. Теорема о контекстно-свободном языке. Пусть L — контекстно-свободный язык над алфавитом Σ. Тогда найдётся такое натуральное число p, что для любого слова w ∈ L длины не меньше p найдутся слова u, v, x, y, z ∈ Σ^∗, для которых верно uvxyz = w, vy ≠ ε (то есть v ≠ ε или y ≠ ε), |vxy|≤p и uvⁱxyⁱz ∈ L для всех i ∈ N. Пример: Язык: L={0­ⁿ1ⁿ2^n­ | n≥1}. z = 0­ⁿ1ⁿ2^i­ =uvwxy, где n – характеристика CFL. Возможные варианты разбиения: vwx не содержит 2; vwx не содержит 0; vwx содержит только 1.

22 Свойства замкнутости класа контекстно-свободных языков.

Теорема 1. Если L — контекстно-свободный язык, то L^∗ тоже контекстно-свободный язык. Доказательство. Пусть язык L порождается грамматикой <N, Σ,P,S>. Тогда язык L^∗ порождается грамматикой <N ∪{ T }, Σ,P ∪{ T → ST, T → ε},T >,где T не ∈ N ∪ Σ. Теорема 2. Если L₁ и L₂ — контекстно-свободные языки над алфавитом Σ,то L₁ · L₂ тоже контекстно-свободный язык. Доказательство. Пусть язык L₁ порождается грамматикой <N₁, Σ,P₁,S₁> и L₂ порождается грамматикой <N₂, Σ,P₂,S₂>, где N₁ ∩ N₂ = ∅.Тогда L₁ · L₂ порождается грамматикой <N₁∪ N₂∪{ T }, Σ,P₁∪ P₂∪{ T → S₁S₂},T >,где T не ∈ N₁∪ N₂∪ Σ. Теорема 3. Если L₁ и L₂ — контекстно-свободные языки над алфавитом Σ,то L₁ ∪ L₂ тоже контекстно-свободный язык. Доказательство. Пусть язык L₁ порождается грамматикой <N₁, Σ,P₁,S₁> и L₂ порождается грамматикой <N₂, Σ,P₂,S₂>, где N₁ ∩ N₂ = ∅.Тогда L₁ ∪ L₂ порождается грамматикой <N₁ ∪ N₂ ∪{ T }, Σ,P₁ ∪ P₂ ∪{ T → S₁,T → S₂},T >,где T не ∈ N₁ ∪ N₂ ∪ Σ. Теорема 4. Если L — контекстно-свободный язык, то L^R тоже контекстно-свободный язык.

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

Теорема 1. Если L₁ и L₂ — линейные языки над алфавитом Σ,то L₁ ∪ L₂ тоже линейный язык. Доказательство. Пусть язык L₁ порождается грамматикой <N₁, Σ,P₁,S₁> и L₂ порождается грамматикой <N₂, Σ,P₂,S₂>, где N₁ ∩ N₂ = ∅.Тогда L₁ ∪ L₂ порождается грамматикой <N₁ ∪ N₂ ∪{ T }, Σ,P₁ ∪ P₂ ∪{ T → S₁,T → S₂},T >,где T не ∈ N₁ ∪ N₂ ∪ Σ. Пример. Рассмотрим алфавит Σ= { a, b, c}.Язык L =Σ^∗ −{ aⁿbⁿcⁿ | n >=0} является линейным, поскольку L = L₁ ∪ L₂ ∪ (Σ^∗ − L₃), где языки L₁ = { a^mbⁿc^k | m ≠ n, k >= 0}и L₂ = { a^mbⁿc^k | n ≠ k, m >= 0} являются линейными, а язык L₃ = { a^mbⁿc^k | m >= 0,n >= 0,k >= 0} является автоматным и можно применить теорему 1:Каждый автоматный язык является право-линейным; и теоремму 2: Если L1 и L2 — линейные языки над алфавитом Σ,то L1 ∪ L2 тоже линейный язык

24 Свойства замкнутости регулярных языков.

Класс языков, распознаваемых конечными автоматами, замкнут относительно: а)объединения; б)конкатенации; в)навешивания звездочки Клини; г)взятия дополнения; д)пересечения. Д/во: мы должны показать, что если есть два языка, распознаваемых автоматами M1 и M2, то существует автомат M, распознающий язык, получающийся из 2х предыдущих (для навешивания звездочки Клини и взятия дополнения из языка, распознаваемого автоматом M1) с помощью рассматриваемой операции. а) Объединение. мн-ва K1 и K2 не пересекаются. Тогда автомат M, распознающий язык L(M1) ∪ L(M2): M = <K, Σ, ∆, s, F>, где s -новое состояние, не входящее ни в K1, ни в K2, K = K1 ∪ K2 ∪ {s}, F = F1 ∪ F2, ∆ = ∆1 ∪ ∆2 ∪ {<s, e, s1>, <s, e, s2>}. Если w ∈ Σ∗, то <s, w> |-∗M <q, e> для некоторого q ∈ F тогда и только тогда, когда или <s1, w> |-∗M1 <q, e> для некоторого q ∈ F1, или <s2, w> |-∗M2 <q, e> для некоторого q ∈ F2. M распознает w тогда и только тогда, когда или M1 распознает w, или M2 распознает w, и L(M) = L(M1) ∪ L(M2). б) Конкатенация. пусть M1 и M2 - НДА; построим НДА M такой, что L(M) = L(M1) ◦ L(M2). M вначале имитирует работу M1, а затем недетерминированно прыгает из конеч сост M1 в нач сост M2, после чего имитирует работу M2. в) Навешивание звездочки Клини. Пусть M1 - НДА. Построим НДА M такой, что L(M) = L(M1)∗. M состоит из сост M1 и всех переходов M1; любое конеч сост M1 является конеч сост M. в M есть новое нач сост s1. Новое нач сост также является конечным, поэтому пустое слово распознается. Из s'1 существует e-переход в s1 начальное состояние M1, поэтому имитация работы M1 может начаться как только M начнет работу из состояния s1. Кроме того, из каждого конечного состояния M1 добавлен e-переход обратно в s1, поэтому как только прочитывается слово из L(M1), автомат может перейти в нач сост автомата M1. г) Взятие дополнения. Пусть M = <K, Σ, δ, s, F> ДКА. Тогда язык L =Σ∗ \ L(M) распознается ДКА M = <K, Σ, ∆, s, K \ F>. Иными словами, M идентичен M с точностью до взаимозамены конечных и неконечных состояний. д) Пересечение. заметим, что L1 ∩ L2 = Σ∗ \ ((Σ∗ \ L1) ∪ (Σ∗ \ L2)), и потому замкнутость относительно пересечения следует из замкнутости относительно объединения дополнения, т.е. из пунктов а) и г). #

25 Теорема Майхилла-Нероуда.

Пусть L ∑* - регулярный язык. Тогда существует DFA, распознающий язык L, который имеет в точности столько состояний, ск-ко имеется классов эквивалентности в отношении ≈L. Д-во: обозначим класс эквивалентности отношения ≈L, в который попадает слово хÎ∑*, через [x]. Дан язык L, сконструируем DFA М=<K,∑,d,s,F >такой, что L=L(М). Который определен так: K={[x]|xÎ∑*}-мн-во классов эквивалентности от-но ≈L. s=[e]-класс эквивалентности, содержащий пустое слово. F={[x]|xÎL}. и для всех [x]ÎK и для всех аÎ∑ полагаем d([x],a)=[xa]. Язык L регулярен, следовательно распознается неким DFA M’. А отношение ~M’ имеет больше классов эквивалентности, чем ≈L. Значит, мн-во К – конечно. Нужно также показать, что d правильно определена, то есть что d([x],a)=[xa] независимо от выбора слова xÎ[x]. Но это следует из того, что х≈Lх’ тогда и только тогда когда ха≈Lх’а. Осталось показать, что L=L(M). Покажем, что для всех x,yÎ∑* <[x],y> |-*M <[xy],e> выполняется по индукции по |y|. Когда у=е – это тривиально, а если отношение установлено для всех слов длины n и y=y’a, то по индукции <[x],y> |-*M <[xy],e>. Из доказанного=> для всех xÎ∑* мы имеем, что xÎ L(M) тогда и только тогда, когда <[e],x> |-*M <[q],e> для некого qÎF, что по доказанному равносильно тому, что [x]ÎF, или, по определению F, равносильно тому, что что xÎ L. Что и требовалось доказать. Следствие: Язык L регулярен тогда и только тогда, когда отношение ≈L имеет конечное число классов эквивалентности.

26 Теорема о накачке (pumping).

Пусть L-регулярный язык. Тогда существует число n>=1 такое, что любое слово ωÎL такое, что |ω|>=1, может быть переписано как ω=xyz так, что y≠e, |xy| <=n и xyizÎLдля каждого i>=0. Д-во: Так как язык регулярен, то он распознается DFA M. Предположим, что n-конечное число состояний M, и пусть ω – слово длины n или |ω|=m>==n. Работа автомата M при вводе слова ω: <q0, ω1 ω2…. ωm> |-M<q1, ω2…. ωm>|-M…|-M<qm,e>, где q0-начальное состояние M, а ω1 …. ωm – первые m символов слова ω. Так как у M всего n состояний, а в указанном вычислении возникает как минимум n+1. конфигурация вида <qi, ωi+1…. ωm>, то существует числа i и j такие, что0<=i<j<=n и qi=qj. Иными словами, слово y= ωiωi+1…. ωm переводит M из состояния qiназад в состояние qj, и это слово непустое, так как i<j. Но тогда это подслово можно удалить из ω или наоборот, повторить в ω ск-ко угодно раз сразу после j-го символа ω, и М все равно будет распознавать это слово. Таким образом, М распознает xyizÎL для каждого i>=0, где x= ω1…. ωi, а z=ωi+1…. ωm. Заметим, что длина слова xy, которую мы ранее обозначили j, по определению не более n, что и требовалось доказать. Пример: язык L={aibi|i>=0}не является регулярным, так как если бы он был регулярен, то теорема о накачке выполнялась бы для некого n. Рассмотрим тогда слово ω= anbnÎL. По теореме оно может быть написано в виде ω=xyz так, что |xy|<=n и y≠e – т.е, y=ai для некого i>0. Но тогда xz=an-ibn не принадлежит L, что противоречит теореме.

27 Теорема о разрастании (накачке - pumping) для (CFL) контекстно-свободных языков.

Пусть L — контекстно-свободный язык над алфавитом Σ. Тогда найдётся такое натуральное число p, что для любого слова w ∈ L длины не меньше p найдутся слова u, v, x, y, z ∈ Σ^∗, для которых верно uvxyz = w, vy ≠ ε (то есть v ≠ ε или y ≠ ε), |vxy|≤p и uvⁱxyⁱz ∈ L для всех i ∈ N. Доказательство. Пусть язык L порождается грамматикой в нормальной форме Хомского G = <N,Σ, P, S>. Индукцией по k легко доказать, что для любого дерева вывода в грамматике G длина кроны дерева не превышает 2^k−2, где k — количество вершин в самом длинном пути, начинающемся в корне дерева и заканчивающемся в некоторой вершине, помеченной символом из Σ. Положим p = 2^|N|. Пусть w ∈ L и |w| ≥p. Зафиксируем некоторое дерево вывода с кроной w в грамматике G. Рассмотрим самый длинный путь в этом дереве. Этот путь содержит не менее |N|+2 вершин. Среди них найдутся две вершины с одинаковыми метками, причём их можно выбрать среди последних |N| + 2 вершин рассматриваемого пути. Выберем слова u, v, x, y и z так, что uvxyz = w, поддерево с корнем в одной из найденных вершин имеет крону x и поддерево с корнем в другой найденной вершине имеет крону vxy. Из того что G — грамматика в нормальной форме Хомского, заключаем, что vxy ≠ x. Неравенство |vxy| ≤ 2^|N| следует из того, что самый длинный путь в соответствующем слову vxy поддереве содержит не более |N|+2 вершин. Для каждого i ∈ N можно построить дерево вывода с кроной uvⁱxyⁱz, комбинируя части исходного дерева вывода.

28 Теорема о существовании эвивалентных автоматов.

Теорема: Для каждого НДА существует эквивалентный ДКА. Д/во: Пусть M = <K, Σ, ∆, s, F> - НДА. хотим сконструировать ДКА M = <K', Σ', δ, s', F'>, эквивалентный M. если M имеет пять состояний {q0,..., q4} и после прочтения некоторого слова может оказаться в состояниях q0, q2 или q3, но не q1 или q4, то в качестве его текущего состояния надо рассматривать множество {q0, q2, q3}, а не неопределенный элемент этого множества. И если следующий вводимый символ может перевести M из q0 в q1 или q2, из q2 в q0, а из q3 в q2, то в качестве следующего состояния M следует рассматривать множество {q0, q1, q2}. Мн-вом состояний M будет K' = 2^k мн-во подмн-в мн-ва состояний M. Мн-во конечных состояний M будет состоять из тех подмн-в K, которые содержат хотя бы одно конечное состояние M. Определение функции перехода для M' будет немного более сложным. Базовая идея заключается в том, чтобы машина M при чтении символа a ∈ Σ имитировала бы действие машины M при чтении символа a, возможно, следующего после любого количества срабатываний M при вводе пустого слова. Для любого состояния q ∈ K будем обозначать через E(q) множество всех состояний M, которые достижимы из состояния q без чтения ввода. То есть, E(q) = {p ∈ K|<q, e> |-∗M <p, e>}. Таким образом, E(q) может быть вычислено по следующему алгоритму: изначально полагаем E(q):= {q}; while существует переход <p, e, r> ∈ ∆ с p ∈ E(q) и r ∉ E(q) do E(q):= E(q) ∪ {r}; Каждое выполнение цикла while добавляет еще одно состояние к E(q), и их не может быть добавлено больше, чем имеется всего состояний, поэтому данный алгоритм заканчивает работу самое большее после |K| итераций.

29 Характеризация контекстно-свободных грамматик. Взаимо связь между автоматами со стеком и контекстно-свободными граматиками.

Теорема. Если язык L является контекстно-свободным, то существует МП-автомат, распознающий этот язык. Доказательство. Пусть язык L порождается грамматикой <N, Σ,P,S>, в которой каждое правило имеет вид A → wβ, где A ∈ N, w ∈ и β ∈ . Положим Γ= N, Q = { 1, 2}, I = { 1}, F = { 2} и Δ= {<<1,ε,ε>, <2,S>>} ∪ { <<2,w,A>,<2,β>> | (A → wβ) ∈ P }.Можно доказать, что <2,u,s> <2,ε,α> тогда и только тогда, когда существует левосторонний вывод S uα (здесь u ∈ и α ∈ ). Лемма. Каждый МП-автомат эквивалентен некоторому МП-автомату <Q, Σ, Γ, Δ,I,F>,где |I| =1, |F | =1 и каждый переход <<p, x, β>,< q, γ>> ∈ Δ удовлетворяет требованиям |x| 1 и |β| + |γ| =1. Пример. Рассмотрим МП-автомат M = <Q, Σ, Γ, Δ,I,F >,где Q = I = F = { 1}, Σ= { a, b, c, d}, Γ= { A, B}, Δ= {<<1,a,A>, <1,ε>>, <<1,b,B>, <1,ε>>, <<1,c,ε>, <1,A>>, <<1,d,A>, <1,AB>>}. Он эквивалентен МП-автомату = < , Σ, Γ, ,I,F >, где = = { 1, 2, 3} и {<<1,a,A>, <1,ε>>, <<1,b,B>, <1,ε>>, <<1,c,ε>, <1,A>>, <<1,d,A>, <2,ε>>, <<2,ε,ε>, <3,B>>, <<3,ε,ε>, <1,A>>}. Теорема. Если язык L распознаётся некоторым МП-автоматом, то L является контекстно-свободным. Доказательство. Пусть язык L распознаётся МП-автоматом <Q, Σ, Γ, Δ,I,F >. Без ограничения общности можно считать, что I = { qs}, F = { qa} и каждый переход <<p, x, β>, <q, γ>> ∈ Δ удовлетворяет требованию |β| + |γ| =1. Построим искомую контекстно-свободную грамматику <N, Σ,P,S>, положив N = { | p ∈ Q, q ∈ Q}, S = и P = { → ε | p ∈ Q} ∪ { → x , y |<<p, x, ε>, <q, C>> ∈ Δ, <<r, y, C>, <s, ε>> ∈ Δ,C ∈ Γ,t ∈ Q}. Можно доказать, что <p, x, ε> <q, ε, ε> тогда и только тогда, когда x (здесь x ∈