Операции над языками (1134708), страница 3
Текст из файла (страница 3)
В качестве синонима в настоящее время используется более современный термин конечный преобразователь (finite transducer — ft).124состояние ; F ⊆ Q — множество конечных состояний. Запись (p, w) ∈ δ(q, a)означает, что S в состоянии q, имея на входе символ a, может в качестве одногоиз возможных вариантов движения перейти в состояние p и вывести строку w.Мы расширим область определения δ до Q × Σ* следующим образом:δ(q, ε) = {(q, ε)},δ(q, xa) = {( p, w) | w = w1w2, ( p’, w1) ∈ δ(q, x) и ( p, w 2) ∈ δ( p’, a)}, если x ∈ Σ*и a ∈ Σ.Определение 9.6.
Пусть S — обобщенная последовательная машина иS (x) = { y | ( p, y) ∈ δ(q 0 , x) для некоторого p ∈ F}. Если L есть язык над Σ, тоS (L) = { y | y ∈ S (x) для некоторого x ∈ L} называется gsm-отображением, аS –1(L) = { y | x ∈ S (y) для некоторого x ∈ L} — обратным gsm-отображением.Не обязательно истинно, что S –1(S (L)) = S (S –1(L)) = L, и потому отображение–1S не является подлинно обратнымПример 9.3. Пусть S = ({q 0, q1}, {0, 1}, {a, b}, δ, q 0, {q1}) — обобщенная последовательная машина, где отображение δ определено следующим образом:1) δ(q 0, 0) = {(q0, aa), (q1, b)},2) δ(q 0, 1) = {(q0, a)},3) δ(q 1, 0) = ∅,4) δ(q 1, 1) = {(q1, ε)}.1(a)q00(aa)Рис. 9.2.0(b)q1Интуитивно, пока в gsm S вводятся нули (рис.
9.2), gsm S имеет выбор: выводить два символа a либо один символ b. Если gsm S выводит b, она переходит всостояние q 1. Если gsm S находится в состоянии q 0 и в нее вводится символ 1, тоона может выводить только символ a. В состоянии q 1 gsm S ничего не может поделать с 0 на входе, но может оставаться в состоянии q 1 без какого-либо вывода,если на входе 1.n nПусть L = {0 1 | n ≥ 1}.
Тогда S (L) = {a 2nb | n ≥ 0}.iЕсли обозначить S (L) при помощи L1, то S –1(L1) = {w 01 | i ≥ 0 и w имеет 11четное число 1}. Заметим, что S –1(S (L)) ≠ L.Характерная особенность gsm-отображения и обратного gsm-отображениясостоит в том, что они сохраняют разные классы языков.11При этом w может содержать любое число нулей.125Лемма 9.3. Каждый класс языков, замкнутый относительно конечной подстановки и пересечения с регулярным множеством, замкнут относительноgsm-отображений.Доказательство.
Пусть C — класс языков, замкнутый относительно конечной подстановки (следовательно, также и гомоморфизма) и пересечения с регулярным множеством. Пусть S = (Q, Σ, ∆, δ, q0, F) — обобщенная последовательная машина. Определим конечную подстановкуf (a) = {[q, a, x, p] | q, p ∈ Q, a ∈ Σ, x ∈ ∆*, и ( p, x) ∈ δ(q, a)}.Пусть R — регулярное множество, содержащее все строки вида[q 0, a 1, x1, q 1] [q 1, a 2, x 2, q 2]…[q n – 1, a n , x n , q n ],такие, что для 1 ≤ i ≤ n, a i ∈ Σ, x i ∈ ∆*, q i ∈ Q, (q i , x i ) ∈ δ(qi – 1, a i ).
Также q 0 — начальное состояние и q n ∈ F. Пусть h ([q, a, x, p]) = x для всех [q, a, x, p].Теперь для L ∈ C имеем S (L) = h ( f (L) ∩ R). Поскольку класс языков C замкнут относительно конечной подстановки и пересечения с регулярным множеством, то язык S (L) тоже находится в C. Заметим, что требуется замкнутость относительно конечной подстановки, а не ε-свободной конечной подстановки, поскольку в [q, a, x, p] цепочка x может быть равна ε, и в этом случаеh ([q, a,x, p]) = ε.Теорема 9.10. Классы регулярных, контекстно-свободных и языков типа 0замкнуты относительно gsm-отображений.Доказательство.
Теорема является прямым следствием леммы 9.3 и теорем 9.4, 9.6 и 9.7.Отметим, что gsm-отображения не сохраняют контекстно-зависимых языков,поскольку каждый гомоморфизм является gsm-отображением.Определение 9.7. Говорят, что gsm-отображение ε-свободно, если (p,ε)∉ δ(q, a)для любых q, p ∈ Q и a ∈ Σ.Хотя контекстно-зависимые языки не замкнуты относительно произвольныхgsm-отображений, они замкнуты относительно ε-свободных gsm-отображений.Теорема 9.11. Класс контекстно-зависимых языков замкнут относительноε-свободных gsm-отображений.Доказательство. В лемме 9.3 конечная подстановка может быть замененана ε-свободную конечную подстановку при условии, что gsm-отображениеεсвободно.
Таким образом, поскольку класс контекстно-зависимых языков замкнут относительно ε-свободной конечной подстановки и пересечения с регулярным множеством, то этот класс замкнут относительно ε-свободныхgsmотображений.Рассмотрим теперь обратные gsm-отображения. Как увидим, регулярные,контекстно-свободные, контекстно-зависимые и языки типа 0 все замкнуты относительно обратных gsm-отображений.126Лемма 9.4. Пусть C — класс языков, замкнутый относительно ε-свободной подстановки, k-ограниченного стирания и объединения и пересечения с регулярными множествами.
Тогда класс C замкнут относительно обратных gsmотображений.Доказательство. Пусть L ⊆ ∆* есть язык в классе C, а S = (Q, Σ, ∆, δ, q 0, F)— обобщенная последовательная машина. Мы предполагаем без потери общности, что Σ ∩ ∆ = ∅. Определим подстановку f следующим образом: f (b) = Σ *bдля каждого b ∈ ∆. (Отметим, что замкнутость относительно объединения и пересечения с регулярными множествами гарантирует принадлежность всех регулярных множеств классу C и, следовательно, Σ *b ∈ C .)Пусть L1 = f (L) ∪ Σ *, если ε ∈ L, и L1 = f (L) в противном случае.
Тогда L естьмножество всех строк вида y 1 b 1 y 2 b 2 … yr b r , r ≥ 1, где bi ∈ ∆, yi ∈ Σ *, 1 ≤ i ≤ r,b1b 2…br ∈ L, объединенное с Σ *, если ε ∈ L. Применим теперь лемму 9.3 к классам регулярных, контекстно-свободных и языков типа 0.Пусть R — регулярное множество, состоящее из всех слов вида a 1 x 1 a 2 x 2 …a m x m, m ≥ 0, таких, что1) ai ∈ Σ;2) xi ∈ ∆*, 1 ≤ i ≤ m.Существуют состояния q 0, q 1,…, q m, такие, что q m ∈ F и (q i, x i) ∈ δ(q i – 1, a i) для1 ≤ i ≤ m.Заметим, что цепочка x i может быть равна ε. Нетрудно показать путем построения конечного автомата, принимающего R, что R — регулярное множество.Теперь L1 ∩ R есть множество всех слов вида a1 x1 a2 x2 … am xm, m ≥ 0, гдеa i ∈ Σ, x i ∈ ∆*, 1 ≤ i ≤ m, x1 x 2 … x m ∈ L, S (a 1 a 2 … a m) содержит цепочку x1 x 2 … x m, ини одна цепочка x i не длиннее, чем k, причем k — длина самой длинной цепочкиx, такой, что ( p, x) ∈ δ(q, a) для некоторых состояний p, q ∈ Q и a ∈ Σ.Наконец, пусть h — гомоморфизм, который отображает символ a в a для каждого a ∈ Σ и символ b — в ε для каждого b ∈ ∆.
Тогда S –1(L) = h (L1 ∩ R) находится в классе C, поскольку h никогда не отображает больше k последовательных символов в ε.Теорема 9.12. Классы регулярных, контекстно-свободных, контекстнозависимых и языков типа 0 замкнуты относительно обратных gsm-отображений.Доказательство следует непосредственно из леммы 9.4 и того факта, чтоназванные классы замкнуты относительно ε-свободной подстановки, k–ограниченного стирания, а также пересечения и объединения с регулярныммножеством.Теперь рассмотрим операцию деления.Определение 9.8.
Пусть L1 и L2 — любые два языка. Определим частное отделения L1 на L2 как множество {x | для некоторой цепочки y ∈ L2, такой, чтобыxy ∈ L1}.127Пример 9.4. Пусть L1 = {a nb n | n ≥ 1} и L 2 = b*. ТогдаL1 / L2 = {a i b j | i ≥ j, i ≥ 1 }, а L2 / L1 = ∅.Лемма 9.5. Каждый класс языков, замкнутый относительно конечной подстановки и пересечения с регулярным множеством, замкнут относительно деления на регулярное множество.Доказательство.
Пусть C — класс языков, замкнутый относительно названных операций. Пусть L ∈ Σ 1* — язык из класса C и R ⊆ Σ 1*— регулярноемножество. Пусть Σ 2 = {a’| a ∈ Σ 1} и f — конечная подстановка: f (a) = {a, a’}.Рассмотрим L2 = Σ 2* R ∩ f (L). Пусть h — гомоморфизм, определяемый следующим образом: h ( a) = ε и h ( a’) = a для всех a ∈ Σ 1. Теперь L / R = h (L2). Поскольку класс C замкнут относительно конечной подстановки и пересечения с регулярным множеством, то L / R находится в классе C.Теорема 9.13.
Классы регулярных, контекстно-свободных и языков типа 0замкнуты относительно деления на регулярное множество.Доказательство следует непосредственно из леммы 9.5.На вопрос: замкнут ли класс контекстно-зависимых языков относительноделения на регулярное множество, ответим — нет.Теорема 9.14. Если L1 есть любой язык типа 0, то существует контекстно-зависимый язык L2 и регулярное множество R, такие, что L1 = L2 / R.Доказательство почти идентично доказательству теоремы 9.9. Пусть G 1 =(VN, VT, P1, S 1) — грамматика типа 0, такая, что L(G1) = L1 и пусть G2 =(VN ∪ {S 1, D}, VT ∪ {c, d }, P2, S 2), где P2 определяется следующим образом:1) если α → β ∈ P1 и | α | ≤ | β |, то α → β ∈ P2 ;i2) если α → β ∈ P1 и | α | – | β | = i, i > 0, то α → βD ∈ P2 ;3) для всех A ∈ VN и a ∈ VT существуют правила DA → AD и Da → aD ∈ P2 ;4) существуют правила Dc → cc и Dc → dc ∈ P2 ;5) существует правило S 2 → S 1Dc ∈ P2.Обратим внимание читателя на сходство L(G2) с языком, определенным втеореме 9.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
