Операции над языками (1134708), страница 2
Текст из файла (страница 2)
Класс языков типа 0 и класс контекстно-зависимых языковзамкнуты относительно пересечения.Доказательство. Пусть L1 и L2 — языки типа 0 (контекстно-зависимыеязыки). Рассмотрим две одноленточные машины Тьюринга (два недетерминированных линейно ограниченных автомата) M1 и M2, принимающие языки L1 и L2соответственно. Легко построить машину Тьюринга (lba) M, имеющую однуоперативную ленту с тремя дорожками.
Первая дорожка содержит ввод. Машина M моделирует машину M1, используя дорожку 2. Если машина M1 достигаеткогда-либо принимающую конфигурацию, то машина M перемещает головкусвоей ленты на левый конец и моделирует машину M2 на дорожке 3. Если машина M2 доходит до принимающей конфигурации, то машина M принимает.§ 9.2.
Замкнутостьотносительно отображенийТеперь рассмотрим результаты отображений разных типов над языками.Первый тип, который мы рассмотрим, — подстановка.Определение 9.1. Подстановка f есть отображение конечного множества Σна подмножества ∆* некоторого конечного множества ∆. Другими словами, подстановка f с каждым символом из множества Σ ассоциирует некоторый язык.Отображение f может быть распространено на строки из Σ* следующим образом:f (ε) = ε, f (xa) = f (x) f (a), где x ∈ Σ*, a ∈ Σ.120Очевидно, что f (x) нужно понимать в обобщенном смысле, тогда как f (a) — впервоначальном.Мы можем распространить подстановку f далее на языки, определяяf (L) = ∪ f ( x) .x ∈LПример 9.1.
Пусть f (0) = {a}, f (1) = {ww R | w ∈ {b, c}*}. Подстановка fn nотображает множество {0 1 | n ≥ 1} в множество {a nw1w1Rw2w2R…wnwnR | wi ∈ {b, c}*для 1 ≤ i ≤ n}.Говорят, что класс языков замкнут относительно подстановки, если длялюбого языка L ⊆ Σ* в данном классе и для любой подстановки f, такой, что f (a)в данном классе для всех a ∈ Σ, язык f (L) содержится в этом же классе.Покажем, что классы регулярных множеств, контекстно-свободных языков иязыков типа 0 замкнуты относительно подстановки.
Так, в примере 9.1, поскольn nку f (0) и f (1) — оба контекстно-свободные языки и так как L = {0 1 | n ≥ 1} —контекстно-свободный язык, то множество f (L) = {a nw1w1Rw2w2R…wnwnR | wi ∈ {b,c}* для 1 ≤ i ≤ n} также контекстно-свободный язык.Теорема 9.7. Классы регулярных множеств, контекстно-свободных языкови языков типа 0 замкнуты относительно подстановки.Доказательство. Рассмотрим грамматику G = (VN, {a 1, a 2,…, a n}, P, S).Пусть Gi = (VNi , VTi , Pi , Si) — грамматика, порождающая множество f (a i) для каждого i, 1 ≤ i ≤ n.
Без потери общности предполагаем, что все нетерминальныесловари попарно не пересекаются.Докажем теорему для случая, когда грамматики G и Gi, 1 ≤ i ≤ n , являютсяконтекстно-свободными. Читатель может доказать другие случаи аналогично,хотя в каждом необходимы дополнительные детали.Построим новую грамматику:G’= (VN’, VT’, P’, S ), где VN’= VN ∪n∪ VNi , VT’=i =1n∪VTi.i =1Пусть h — подстановка h (a i ) = {S i} для 1 ≤ i ≤ n и h (A) = {A} для любогоA ∈ VN; P’=n∪Pi∪ {A → h (α) | A → α ∈ P}. Ясно, что грамматика G’являетсяi =1контекстно-свободной, возможно, с правилами вида A → ε.
Очевидно, чтоf (L(G )) = L(G’).n nПример 9.2. Пусть L = {0 1 | n ≥ 1}. Язык L порождается грамматикойG = ({S}, {0, 1}, {S → 0S1, S → 01}, S ).Как и в примере 9.1, пустьf (0) = {a} и f (1) = {wwR | w ∈ {b, c}*};f (0) порождается грамматикойG1 = ({S1}, {a}, {S → a}, S 1),121а f (1) — грамматикойG 2 = ({S2}, {b, c}, {S 2 → bS 2 b, S2 → cS 2c, S 2 → ε}, S 2).Язык f(L) порождается грамматикой G3 = ({S, S1, S 2}, {a, b, c}, {S → S1SS 2, S → S1S 2,S1 → a, S 2 → bS 2 b, S2 → cS 2c, S2 → ε}, S).
Первые два правила грамматики G3получились из правил S → 0 S 1 и S → 01 грамматики G1 в результатеподстановки символа S1 вместо 0 и символа S 2 — вместо 1.Контекстно-зависимые языки не замкнуты относительно подстановки. Однако мы можем несколько смягчить этот факт.Определение 9.2. Подстановка f называется ε-свободной (ε-free), еслиε ∉ f (a) для каждого a ∈ Σ.Теорема 9.8. Класс контекстно-зависимых языков замкнут относительноε-свободной подстановки.Доказательство. Рассмотрим контекстно-зависимую грамматику G = (VN,{a 1, a 2 ,…, a n}, P, S ) и ε-свободную подстановку f.
Пусть для каждого i,1 ≤ i ≤ n, Gi = (VNi, VTi, Pi, Si) — контекстно-зависимая грамматика, порождающаямножество f (a i). Без потери общности предполагаем, что все нетерминальныесловари попарно не пересекаются. Кроме того, предполагаем, что все правила,за возможным исключением S → ε, имеют вид α → β или A → a, где α, β — непустые строки нетерминалов, A — отдельный нетерминал, а a — отдельныйтерминальный символ. Мы построим грамматику G’= (VN’, VT’, P’, SL ), где1. VN’= VN ∪n∪VNi∪ {AL | A ∈ VN }.i =1n2.
VT’= ∪ VTi .i =13. P’содержита) S L → ε, если S → ε ∈ P;б) ALα → BLβ и Aα → Bβ, если Aα → Bβ ∈ P (заметим, что индекс L в обозначении AL помечает самое левое вхождение соответствующего нетерминального символа в выводе в грамматике G до тех пор, пока этот символ не превратится в терминальный символ);в) AL → S i , если A → a i ∈ P,aA → aS i для всех a ∈ VT’, если A → a i ∈ P;г) все правила из множества {Pi | i = 1, 2,…, n}.Грамматика G’— контекстно-зависимая и L(G’) = f (L(G )).Теорема 9.9. Класс контекстно-зависимых языков не замкнут относительно подстановки.Доказательство.
Пусть G1 = (VN, VT, P1, S) — грамматика типа 0, такая, чтоL(G1) не является контекстно-зависимым языком. Снова мы предполагаем без+потери общности, что все ее правила имеют вид α → β или A → a, где α ∈ VN ,β ∈ VN*, A ∈ VN, a ∈ VT.122Пусть c — новый символ.
Рассмотрим грамматику G2 = (VN, VT ∪ {c}, P2, S ), вкоторой P2 содержит1) α → β, если α → β ∈ P1 и |α| ≤ |β| ;2) α → βcc … c, где |α| = |βcc … c |, если α → β ∈ P1 и |α| > |β|;3) cA → Ac для всех A ∈ VN.Грамматика G2 является контекстно-зависимой, поскольку мы принудилиправую часть каждого правила иметь, по крайней мере, такую же длину, как левая.
Правила cA → Ac были добавлены для того, чтобы передвигать символы c кправому концу слов так, чтобы выводы в G2 могли происходить, как в грамматике G1.Теперь рассмотрим подстановку f (a) = {a} для a ∈ VT и f (c) = {ε}. Тогдаf (L(G2)) = L(G1) и, следовательно, подстановка не сохраняет класс csl.Очень часто интерес представляют подстановки специальных типов.Определение 9.3. Подстановка f называется конечной, если f (a) есть конечное множество для всех a из области определения f. Если f (a) — единственнаястрока, то f — гомоморфизм.Конечная подстановка и гомоморфизм являются специальными классамиподстановок. Из этого мы имеем следующие следствия:Следствие 9.1. Классы регулярных, контекстно-свободных и языков типа 0замкнуты относительно конечной подстановки и гомоморфизма.Доказательство очевидно из теоремы 9.7.Следствие 9.2.
Класс контекстно-зависимых языков замкнут относительноε-свободной конечной подстановки и ε-свободного гомоморфизма.Доказательство очевидно из теоремы 9.8.Следствие 9.3. Класс контекстно-зависимых языков не замкнут относительно конечной подстановки и гомоморфизма.Доказательство. Подстановка, использованная при доказательстве теоремы 9.9, является гомоморфизмом.Мы докажем еще один результат, касающийся подстановок, поскольку оннеобходим для последующей теоремы.Определение 9.4. Класс языков замкнут относительно k-ограниченного стирания, если для любого языка L этого класса и любого гомоморфизма h, обладающего тем свойством, что h никогда не отображает более, чем k последовательных символов любого предложения из языка L в ε, h (L) находится в этом жеклассе.Покажем, что класс контекстно-зависимых языков замкнут относительно kограниченного стирания. Фактически справедливо более общее утверждение.Пусть L ⊆ Σ* — контекстно-зависимый язык и пусть f (a) для любого a ∈ Σ тожеконтекстно-зависим.
Тогда язык f (L) контекстно-зависим при условии, что существует k > 0, такое, что для x ∈ L и y ∈ f (x) выполняется неравенство | y | ≥ k | x |.123Лемма 9.2. Класс контекстно-зависимых языков замкнут относительно kограниченного стирания.Доказательство. Пусть G1 = ( VN(1) , V (1)T , P1, S 1) — контекстно-зависимаяграмматика. Без потери общности предположим, что правила, за возможным+(1)исключением S 1 → ε, имеют вид α → β или A → a, где α, β ∈ VN(1) , A ∈ VN , аa ∈ V (1)T .
Пусть h — гомоморфизм со свойством, что h никогда не отображаетболее, чем k последовательных символов любого предложения x ∈ L(G1) в ε.Пусть целое l больше, чем k + 1, и больше длины самой длинной левой частилюбого правила. Рассмотрим грамматикуG2 = ( VN , V (2)T , P2, S 2),(2)где*VN = {[α] | α ∈ ( VN(1) ∪ V (1)T ) , |α| < 2l },(2)(2)V T содержит такие символы, находящиеся в строках w, что h (a) = w длянекоторого a ∈ V (1)T , S 2 = [S1], а множество правил P2 содержит1) [S1] → ε, если S 1 → ε ∈ P1 или если x ∈ L(G1) и h (x) = ε (заметим, что | x | ≤ k,так что мы можем проверить, существует ли какая-нибудь такая цепочка x);(2)2) [α] → [β] для всех [α] и [β] из VN , таких, что α β и |β| < 2l ;(2)3) [α] → [β1][β2]…[βm] для всех [α], [β1], [β2],…, [βm] из VN , таких, чтоα β1β2 …βm, | βi | = l, 1 ≤ i < m, l ≤ | βm| < 2l ;4) [α1][α2] → [β1][β2]…[βm] для всех [α1], [α2], [β1], [β2],…, [βm] из VN(2) , таких,что α1α2β1β2…βm, l ≤ |α1| < 2l, l ≤ |α2 | < 2l, |βi | = l, 1 ≤ i < m, l ≤ |βm | < 2l ;*5) [x] → h (x) для всех [x] ∈ VN(2) , x ∈ V (1)T , h (x) ≠ ε.Грамматика G2 является контекстно-зависимой и L(G2) = h (L(G1)).
Отметим,что G2 получается путем кодирования блоков по меньшей мере из k + 1 символаграмматики G1 в один символ. Поскольку не более k последовательных терминальных символов грамматики G1 отображаются в ε, то в грамматике G2 никогдане требуется иметь правило, в котором нетерминал, не равный начальному, порождал бы ε.Определение 9.5. Обобщенная последовательная машина (gsm10) есть конечный автомат, который может выводить конечное число символов для каждоговходного символа. Формально обобщенная последовательная машина есть система S = (Q, Σ, ∆, δ, q 0, F ), где Q — состояния ; Σ — входной алфавит ; ∆ — вы*ходной алфавит ; δ — отображение типа Q × Σ → 2Q × ∆ ; q 0 ∈ Q — начальное10Gsm — generalized sequential machine.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
