fl_task10 (1178914)
Текст из файла
Задание 10Преобразование Контекстно-Свободных языковКлючевые слова 1 :язык, контекстно-свободный язык, магазинныйавтомат, грамматика, морфизм, метод математической индукции.1Теорема Хомского-ШютценбержеОбозначим Dn язык правильных скобочных выражений (язык Дика) сn типами скобок. Язык Dn определён над размеченым алфавитом Σ =Σn ∪ Σ̄n – в Σn входят открывающие скобки, в Σ̄n закрывающие.Будем говорить, что КС-язык L ⊆ ∆∗ задан в представлении ХомскогоШютценберже, если определены язык Дика Dn , регулярный язык R ⊆ Σ∗и морфизм h : Σ∗ → ∆∗ и L = h(R ∩ Dn ).Теорема (Хомский, Шютценберже, 1963). Язык L ⊆ ∆∗ является контекстносвободным тогда и только тогда, когда существуют такое n, регулярныйязык R и морфизм h : Σ∗ → ∆∗ , что h(Dn ∩ R) = L.Доказательство.
Пусть КС-язык задан грамматикой G = (N, Σ, P, S),где N – множество нетереминалов, Σ – алфавит, P – правила вывода, а S– аксиома. Без ограничения общности будем считать, что G не содержитε-правил, кроме быть может S → ε, причём тогда нетерминал S большене входит в правые части правил.Зафиксируем язык Dn , где n = |N | + |Σ|.
Поставим в соответствиекаждому элементу X из N ∪ Σ пару скобок [X и X ]. Неформально опишем язык R, описав все регулярные события2 , которые допустимы в R.Сначала опишем вспомогательную конструкцию. Для каждого нетерминала A, определим множество RA , в которое, для каждого правилоA → X1 X2 . . . Xn грамматики G, входит соответствующее слово w =[Xn [Xn−1 . . . [Xn−i . .
. [X1 .RA = {w = [Xn [Xn−1 . . . [Xn−i . . . [X1 | A → X1 X2 . . . Xn ∈ P }12минимальный необходимый объем понятий и навыков по этому разделу)Свойства слов, проверяемые ДКА.1Теперь опишем регулярные события, задающие R.• Любое слово из R начинается со скобки [S ;• После закрывающей скобки ]A идёт слово из RA , где A ∈ N ;• После открывающей скобки [σ может идти закрывающая скобка σ ];• После закрывающей скобки ]X может идти закрывающая скобкаY ], где X, Y ∈ N ∪ T .Таким образом, если слово w лежит в языке Dn ∩ R, то оно являетсякодированием левого вывода некоторого слова u в грамматике G: по подслову ]A [Xn [Xn−1 .
. . [Xn−i . . . [X1 X1 ] однозначно восстанавливается правилоA → X1 X2 . . . Xn . Осталось определить морфизм h, который и даёт переход от слова w ∈ R ∩ Dn к слову u ∈ L. Он устроен следующим образом:h(σ ]) = σ ∀σ ∈ Σ, иначе h(X ]) = ε ∀X ∈ N и h([X ) = ε ∀X ∈ N ∪ Σ. Такимобразом мы показали, что любой КС-язык представим в форме ХШ ипривели эффективный алгоритм построения по языку формы ХШ.Пусть теперь язык задан в представлении ХШ (Dn , R, h). Построим по нему МП-автомат, который будет недетерминировано угадыватьпрообраз h−1 (w) слова w и проверять удовлетворяет ли он регулярномуограничению R и является ли он правильным скобочным выражением.Поскольку такой автомат можно построить, то язык, заданный в формеХШ является КС-языком.Упражнение 1.
В доказательстве есть тонкое место про кодированиелевого вывода. Для достаточной строгости это утверждение надо доказать по индукции. Проведите это доказательство.Аккуратно и понятно это сделать не очень просто. См. доказательства в следующем разделе, которые я постарался сделать законченными– идея в доказательстве упражнения такая же, как и в обосновании корректности алгоритма построения грамматики по МП-автомату.2От МП-автоматов к КС-грамматикамОпишем алгоритм построения КС-грамматики G по N -автомату3 M =(Σ, Γ, Q, q0 , Z0 , δ, ∅). G = (N, T, P, S), причём3допускающему по пустому стеку2• T = Σ;• N = {[qZp] | q, p ∈ Q, Z ∈ Γ}• Если δ(q, u, Z) ` (q1 , Y1 , Y2 , .
. . Yn ), то P содержит правила [qZp] →u[q1 Y1 r1 ][r1 Y2 r2 ] . . . [rn−2 Yn−1 rn−1 ][rn−1 Yn p], u ∈ Σ∪ε, для всевозможных наборов состояний r1 , r2 , . . . , rn−1 ∈ Q. Если δ(q, u, Z) = (p, ε),то P содержит правило [qZp] → u.• ∀p ∈ Q S → [q0 Z0 p] ∈ P .Обратите внимание, что слова u и v которые будут фигурироватьдальше в правилах либо буквы, либо пустые слова. Идея алгоритма состоит в том, что левый вывод слова w в грамматике G соответствуетуспешной последовательности конфигураций на входе w автомата M .Состояние q в первом слева нетерминале и есть состояние, в которомнаходится автомат при обработке слова. Если автомат находясь в состоянии q, видя на верхушке стека Z, переходит в состояние q1 , и при этомкладёт что-то в стек, то в выводе грамматики нетерминал [qZp] раскрывается как u[q1 Y1 r1 ][r1 Y2 r2 ] .
. . [rn−2 Yn−1 rn−1 ][rn−1 Yn p], таким образомв выводе грамматики слева опять оказывается текущее состояние автомата q1 , а также в нетерминалах закодировано содержимое его стека.Если же, автомат выталкивает символ Y1 из стека читая v и переходитиз состояния q1 в r1 , то в грамматике есть правило [q1 Y1 r1 ] → v, таким образом [qZp] ⇒L uv[r1 Y2 r2 ] .
. . [rn−2 Yn−1 rn−1 ][rn−1 Yn p] и опять такив промежуточном шаге вывода закодировано текущее состояние автомата и содержание его стека. Вторые состояния в кодировке нетерминалов[qZp] нужны для того, чтобы обеспечить корректность кодировки протокола переходов от одной поверхностной конфигурации к другой.Перейдём к формальной части доказательства.
Покажем что L(M ) ⊆L(G).Утверждение 1. Если (q0 , uv, Z0 ) `∗ (q, v, Y1 Y2 . . . Yn ), тогда для всевозможных состояний r1 , r2 , . . . rn , p ∈ Q справедливоS ⇒∗L u[qY1 r1 ][r1 Y2 r2 ] . . . [rn−2 Yn−1 rn−1 ][rn−1 Yn p].Доказательство. Докажем индукцией по числу тактов k работы автомата M .3База: k = 1. Тогда, (q0 , uv, Z0 ) ` (q, v, Y1 Y2 . . . Yn ), переход происходит заодин такт работы. Построим соответствующий вывод.
Сначала применим правило S → [qZp], а далее раскрываем нетерминал [qZp] – соответствующее правило есть в G по алгоритму построения.Переход: пусть утверждение верно для k = n – покажем, что оно вернодля k = n+1. Пусть (q0 , uv, Z0 ) `∗ (q, v, Y1 Y2 . . . Yn ) и переход выполнен заn + 1 такт работы автомата M . Рассмотрим конфигурацию, соответствующую n-ому такту автомата. Пусть она имеет вид (q1 , ul v, Z1 Z2 . . . ZN )и при этом (q1 , ul v, Z1 Z2 . . . ZN ) ` (q, v, Y1 Y2 .
. . Yn ). По предложению индукции,000S ⇒∗L u1 . . . ul−1 [q1 Z1 r10 ][r10 Z2 r20 ] . . . [rn−2Zn−1 rn−1][rn−1ZN p]За такт работы автомат раскрывает ровно один нетерминал, таким образом автомат делает переход δ(q1 , ul , Z1 ) ` (q, Y1 Y2 . . . Ym ), а Ym+1 =Z2 , Ym+2 = Z3 , . . . Но тогда в грамматике по построению есть правило[q1 Z1 r10 ] → ul [qY1 r1 ][r1 Y2 r2 ] .
. . [rm−1 Ym rm ][r10 Z2 r20 ]Тогда в результате переобозначения нетерминалов и в силу произвольности всех состояний, кроме q получаем, что000S ⇒∗L u1 . . . ul−1 [q1 Z1 r10 ][r10 Z2 r20 ] . . . [rn−2Zn−1 rn−1][rn−1ZN p] ⇒L⇒L u1 . . . ul−1 ul [qY1 r1 ][r1 Y2 r2 ] . . . [rn−2 Yn−1 rn−1 ][rn−1 Yn p].Переход доказан.Из доказанного утверждения в частности следует, что если (q0 , w, Z0 ) `∗(q, ε, ε), то S ⇒L w.
Таким образом, мы показали, что L(M ) ⊆ L(G).Доказательство обратного включения строится в том же духе, что идоказательства приведённых выше утверждений, поэтому его я оставляюв качестве упражнения.Упражнение 2. Доказать, что L(G) ⊆ L(M ).3ЗадачиЗадача 1. Приведите грамматику G к нормальной форме Хомского.Все построения должны быть выполнены строго по алгоритмам. Эквивалентные преобразования допустимы, но если вы их делаете, то вы4должны их явно указать и обосновать их корректность.
Алгоритмы, аналогичные разобранным на семинаре, есть в книжке Хопкрофта Мотвании Ульмана. Грамматика G задана правилами:S → A | B | C | E | AGA → C | aABCB → bABaF | aF CbDaGb | εC → BaAbC | aGD | εF → aBF aaCbA | aGEE → AFЗадача 2∗. Проверьте по алгоритму Кока-Янгера-Касами порождает лиграмматика G из предыдущей задачи слово aabaab.Задача 3. Язык L задан в ХШ-представлении: (D2 , Σ∗ , ϕ), где D2 – языкДика с двумя типами скобок, регулярное ограничение Σ∗ означает, что наслова не накладывается регулярное ограничение, морфизм ϕ определимследующим образом ϕ : [1 → a; 1 ] → b; [2 → b; 2 ] → a. Докажите илиопровергните, что L = {w | |w|a = |w|b }.Задача 4. Возьмите любой детерминированный МП-автомат, допускающий по пустому стеку, как минимум с двумя состояниями, распознающийКС-язык, не являющийся регулярным.
Можете взять язык из примера взадании 7. Постройте по МП-автомату КС-грамматику, сделайте из неёприведённую грамматику. Будет ли она однозначна?5.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
