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 можно повторять сколь угодно много раз или опустить. Тривиальное следствие: в любом бесконечном КС-языке найдется бесконечное подмножество цепочек, длины которых образуют возрастающую арифметическую прогрессию.