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 является автоматным.