Операции над языками (1134708)
Текст из файла
Глава 9ОПЕРАЦИИ НАД ЯЗЫКАМИ§ 9.1. Замкнутостьотносительно элементарных операцийВ этой главе мы применяем операции объединения, конкатенации, обращения, замыкания и т.д. к языкам разных типов. Интересно выяснить, какиеоперации какие классы языков сохраняют, т.е. отображают языки некоторогокласса в тот же самый класс. Есть ряд причин интересоваться этим вопросом.Во-первых, знание, сохраняет операция или нет данный класс языков, помогаетхарактеризовать этот класс.
Во-вторых, часто бывает легче узнать, что сложныйязык относится к некоторому классу, при помощи того факта, что эта принадлежность является результатом различных операций над другими языками вданном классе, чем путем непосредственного конструирования грамматики дляэтого языка. В-третьих, знание, полученное из изучения операций над языками,может быть использовано при доказательстве теорем, как это было сделано в гл.7, где мы показали, что класс рекурсивно перечислимых множеств строго содержит рекурсивные множества, используя при доказательстве тот факт, что рекурсивные множества замкнуты относительно дополнения.Начнем с рассмотрения операций объединения, конкатенации, замыканияКлини и обращения.
Используем следующую лемму о “нормальной форме” дляконтекстно-зависимых языков и языков типа 0:Лемма 9.1. Каждый контекстно-зависимый язык порождается контекстно-зависимой грамматикой, в которой все правила имеют форму либо α → β, гдеα и β — цепочки, состоящие из одних только нетерминалов, либо A → b, где A —нетерминал, а b — терминал. Каждый язык типа 0 порождается грамматикой типа 0, правила которой имеют указанную форму.Доказательство. Пусть G = (VN, VT, P, S) — контекстно-зависимая грамматика. Каждому a ∈ VT сопоставим новый символ Xa. Рассмотрим грамматикуG1 = ( VN' , VT, P1, S), где VN' = VN ∪ {Xa | a ∈ VT}.
Множество P1 включает все правила вида Xa → a. Если α → β ∈ P, то α 1 → β1 ∈ P1, где цепочки α 1 и β1 получаются из цепочек α и β путем замещения в них каждого терминала a символомXa. Доказательство тривиально и мы оставляется его читателю в качестве упражнения. Подобное же доказательство применимо к грамматикам типа 0.Теорема 9.1 Классы регулярных, контекстно-свободных, контекстно-зависимых и рекурсивно перечислимых множеств замкнуты относительно объединения, конкатенации, замыкания и обращения.Доказательство. Для класса регулярных множеств доказательство было дано в гл.
3.117(1)(2)Рассмотрим две грамматики: G1 = ( VN , V T(1) , P1, S 1) и G2 = ( VN , V T(2) , P2 , S 2),причем обе либо контекстно-свободные, либо контекстно-зависимые, либо типа0. Без потери общности можно предполагать, что VN(1) ∩ VN(2) = ∅.Кроме того, согласно лемме 9.1 и теореме 4.5 можно считать, что правилаграмматик G 1 и G 2 имеют форму α → β и A → a, где α и β — цепочки, состоящие из одних только нетерминалов, A — одиночный нетерминал, а a — одиночный терминальный символ. Кроме того, если G1 и G2 — контекстно-свободныеграмматики, то β = ε подразумевает, что α есть S 1 или S 2 и что α никогда не появляется в правой части никакого правила.Объединение.
Пусть G3 = ( VN(1) ∪ VN(2) ∪ {S 3}, V T(1) ∪ V T(2) , P3 , S3), где S 3 ∉(1)(2)VN ∪ VN , а множество P3 содержит правила S 3 → S 1, S 3 → S 2 и все правила измножеств P1 и P2 за исключением S 1 → ε и S 2 → ε, если G1 и G2 — контекстнозависимы. В случае, когда G1 и G2 — контекстно-зависимы и S 1 → ε ∈ P1 илиS2 → ε ∈ P2, добавим правило S 3 → ε к множеству правил P3. Теперь грамматикаG 3 — того же типа, что и грамматики G1, G2, и L(G3) = L(G1) ∪ L(G2).Конкатенация.
Пусть G4 = ( VN(1) ∪ VN(2) ∪ {S 4}, V T(1) ∪ V T(2) , P4 , S4), где S 4 ∉(1)(2)VN ∪ VN , а множество P4 содержит правило S 4 → S 1 S 2 и все правила из множеств P1 и P2, за исключением правил S 1 → ε и S 2 → ε, если G1 и G2 — контекстно-зависимы. В случае, когда G1 и G2 — контекстно-зависимы и S 1 → ε ∈ P1, добавим правило S4 → S 2 к множеству правил P4 ; если S 2 → ε ∈ P2, то добавим правило S 4 → S 1 к множеству P4.
Если S 1 → ε ∈ P1 и S 2 → ε ∈ P2, то добавим правилоS 4 → ε к множеству P4. Теперь грамматика G4 — того же типа, что и грамматикиG1, G2 и L(G4 ) = L(G1)L(G2).SРис. 9.1.αЗаметим, что поскольку VN(1) ∩ VN(2) = ∅ и все правила из множеств P1, P2имеют нетерминалы исключительно слева, невозможно, чтобы строка, образованная правым концом сентенциальной формы грамматики G1, за которой следует левый конец сентенциальной формы грамматики G2, могла быть левой стороной правила в множестве P4.
Это означает, что левая часть любого правила целиком состоит из нетерминалов только одной из двух грамматик (см. рис. 9.1).Соответственно и все правило относится к одной исходной грамматике. Доказательство того, что L(G4 ) = L(G1)L(G2) просто.118Замыкание. Пусть G5 = (VN, V T(1) , P5 , S5), где VN = VN(1) ∪ {S 5, S 5' }, а P5 =P1 ∪ {S5 → S1S5, S5 → ε}, если G5 — контекстно-свободная грамматика, иначеP5 = P1 ∪ {S5 → ε, S5 → S1, S5 → S1 S 5' } ∪ {a S 5' → aS1, a S 5' → aS1 S 5' | a ∈ V T(1) }.Однако в случае, когда G1 — контекстно-зависимая грамматика, правило S1 → ε,если оно имеется, отбрасывается.
Грамматика G5 является грамматикой того жетипа, что и G1, и L(G5) = (L(G1))*.Теперь рассмотрим операции пересечения и дополнения.Теорема 9.2. Класс контекстно-свободных языков не замкнут относительнопересечения.n n ij n nДоказательство. Языки L1 = {a b c | n ≥ 1, i ≥ 0} и L2 = {a b c | n ≥ 1,i ≥ 0} являются контекстно-свободными, поскольку они порождаются грамматиками G1 = ({S, T }, {a, b, c}, {S → Sc, S → T , T → aTb, T → ab}, S ) и G2 = ({S, T },{a , b, c}, {S → aS, S → T , T → bTc, T → bc}, S ) соответственно. Теперь язык Ln n n= L1 ∩ L2 = {a b c | n ≥ 1}, который не контекстно-свободен по тривиальномуследствию из теоремы 4.7.
Действительно, все цепочки L не соответствуют требуемому условию: в L должна быть цепочка uvwxy, такая, что все цепочки видаuv n wx n y при любом n тоже принадлежали бы языку L. Мы могли бы считатьu = y = ε, но ядро w должно быть в первой степени, а в цепочках из языка L онотоже в степени n .Теорема 9.3. Класс контекстно-свободных языков не замкнут относительнодополнения.Доказательство.
Поскольку класс контекстно-свободных языков замкнутотносительно объединения, но не пересечения, то он не может быть замкнут относительно дополнения, поскольку L1 ∩ L2 = L1 ∪ L 2 .Теорема 9.4. Класс контекстно-свободных языков замкнут относительнопересечения с регулярным множеством.Доказательство. Пусть L — контекстно-свободный язык, а R — регулярноемножество. Предположим, что P1 = (QP , Σ, Γ, δP , p 0, Z 0, FP) — недетерминированный магазинный автомат (npda), принимающий язык L, а A = (QA, Σ, δA, q 0, FA )— детерминированный конечный автомат (dfa), принимающий множество R.Построим недетерминированный магазинный автомат (npda) P2 = (QP × QA , Σ, Γ,δ, [p 0, q 0], Z 0, FP × FA ), который принимает L ∩ R.
Функция δ определяется следующим образом. Для всех p ∈ QP, q ∈ QA , a ∈ Σ ∪ {ε} и Z ∈ Γ функция δ([ p, q],a, Z ) содержит ([ p’, δA (q, a)], γ) всякий раз, как δP (p, a, Z ) содержит ( p’, γ). (Напомним, что δA (q, ε) = q для всех q ∈ QA.) Неформально npda P2 хранит след состояний npda P1 и dfa A в своем конечном управлении.I. Предположим, что x ∈ L ∩ R. Пусть x = a 1 a 2 … a n, где a i ∈ Σ ∪ {ε}, 1 ≤ i ≤ n,так что существуют состояния q 0, q1,…, qn ∈ QA , p 0, p1,…, pn ∈ QP и цепочкиγ0,γ1,…,γn ∈ Γ*, для которых имеют место δA (q i, a i + 1) = q i + 1 и (p i , a i + 1…a n, γi)119(p i + 1, a i + 2…a n, γi + 1) при условии, что 0 ≤ i < n, γ0 = Z0, qn ∈ FA, pn ∈ FP. Тогда([ p i, q i], a i + 1…a n, γi ) ([ p i + 1, q i + 1], a i + 2 … a n, γi + 1) и ([ p 0, q0], x, Z 0) ([ pn, qn], ε, γn),при том, что [ pn, qn] ∈ FP × FA , так что x ∈ T (P2).II. Теперь предположим, что x ∈ T (P2).
Тогда существуют движения вида([ p i, q i], a i + 1 … a n, γi ) ([ p i + 1, q i + 1], a i + 2 … a n, γi + 1) для 0 ≤ i < n, причем γ0 = Z0,[ pn, qn] ∈ FP × FA. Тогда δA (q i, a i + 1) = q i + 1 для 0 ≤ i < n, причем qn ∈ FA. Следовательно, x ∈ R. Аналогично ( p i , a i + 1 … a n, γi ) ( p i + 1, a i + 2 … a n, γi + 1) для 0 ≤ i < n и,как следствие, (p 0 , x, Z 0)(pn, ε, γn). Поскольку p n ∈ FP, то x ∈ L .Из рассуждений I и II следует T (P2) = L ∩ R.Мы уже видели в гл. 3, что класс регулярных множеств относительно пересечения и дополнения.
В гл. 7 было показано, что класс рекурсивно перечислимых множеств не замкнут относительно дополнения. Таким образом мы имеем:Теорема 9.5. Класс языков типа 0 не замкнут относительно дополнения.В настоящее время неизвестно, замкнут ли класс контекстно-зависимыхязыков относительно дополнения. Однако как класс языков типа 0, так и классконтекстно зависимых языков замкнуты относительно пересечения. Доказательства для обоих классов аналогичны, и хотя концептуально просты, утомительныв деталях. Поэтому эти доказательства будут только намечены.Теорема 9.6.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
