fl_task7 (1178912)
Текст из файла
Задание 7Контекстно-свободные языки и магазинныеавтоматыКлючевые слова 1 :язык, контекстно-свободный язык, магазинныйавтомат, грамматика, метод математической индукции.1МП-автоматы1.1ОпределенияМоделью вычислений, распознающей класс контекстно-свободных языков (CFL), является автомат с магазинной памятью.Под магазинной памятью понимается стек. Вы должны быть знакомысо стеком из курса информатики, но на всякий случай я скажу про негопару слов. Неформально, стек – это стопка, например такая как колодакарт. Работать со стеком можно следующим образом: карты можно братьтолько последовательно с верхушки колоды – если вы хотите вытащитьвторую карту, то сначала вы должны взять первую, класть карты можнотолько на верх колоды. Сколько карт в колоде вы не знаете, а знаететолько пуста колода или нет.Формально, под стеком понимается следующая структура данных:• элементы стека располагаются в порядке добавления, первый элемент, добавленный в стек называется дном, последний элемент, добавленный в стек, называется верхушкой;• операция push(a) добавляет элемент a в стек, причём a становитсяверхушкой стека;• операция pop() возвращает элемент a, находящийся на верхушкестека;• операция empty() проверяет пустоту стека и возвращает истинноезначение, если стек пуст.1минимальный необходимый объем понятий и навыков по этому разделу)1Магазинные автоматы встречаются куда более чаще, чем стековые, ноназываются они магазинными, потому что на заре этой науки кто-то застолбил название стековые автоматы и под ними стали пониматься такиеавтоматы со стеком, что автомат мог просматривать содержимое стека,не меняя его содержания, а менять его только согласно правилам работысо стеком, что сильно меняло класс языков, распознаваемых автоматом:например, язык an bn cn не распознаётся ни одним МП-автоматом, но распознаётся стековым автоматом.Теперь дадим формальное определение автомату с магазинной памятью.Определение 1.
Магазинный автомат содержит семь компонент и выглядит следующим образом: P = (Σ, Γ, Q, q0 , Z0 , δ, F ), где• Σ – входной алфавит;• Γ – алфавит стека, т.е. символы, которые можно добавлять в стек;• Q – множество состояний автомата;• q0 ∈ Q – начальное состояние автомата;• Z0 ∈ Γ – единственный символ, находящийся в стеке при началеработы автомата;∗• δ : Q × {Σ ∪ ε} × Γ → 2Q×Γ – функия переходов;• F – множество принимающих состояний.В начале работы автомат находится в состоянии q0 и в магазине лежиттолько символ Z0 . за такт работы, автомат считывает букву из входногослова (или же не считывает и тогда выполняет ε-переход) и действует согласно одному из правил перехода.
А именно, пусть автомат находитсяв состоянии q, на верхушке стека лежит символ z ∈ Γ и автомат считывает букву σ. Тогда автомат выбирает одну из пар (q 0 , γ) ∈ δ(q, σ, z),переходит в состояние q 0 , снимает с верхушки символ z и добавляет встек слово γ, причём, если γ = γ1 γ2 . . . γn , то γn оказывается снизу, а γ1сверху. Автомат завершает работу с ошибкой, если не может выполнитьпереход, а входное слово ещё не обработано.2Выделяют два типа магазинных автоматов, которые различаются поусловию приёма входного слова. В первом случае, автомат P принимает слово w, если существует такая последовательность переходов, чтов результате обработки слова, он оказался в принимающем состоянии,в этом случае автомат P является допускающим по заключительномусостоянию. Во втором случае, автомат P принимает слово w, если существует такая последовательность переходов, что в результате2 обработкислова, стек автомата оказался пуст, в этом случае автомат называетсядопускающим по пустому магазину.Замечание 1.
Если δ(q, σ, z) = {(q1 , γ1 ), (q2 , γ2 )}, то автомат выбираетодну из пар и при переходе в состояние q1 автомат помещает в стекγ1 , а при переходе в q2 , автомат помещает в стек γ2 . Автомат неможет перейти в q1 , а в стек положить γ2 !Определение 2. Конфигурацией МП-автомата называется элемент множества Q × Σ∗ × Γ∗ . При начале работы на входе w автомат P находится в конфигурации (q0 , w, Z0 ). За такт работы автомат изменяетконфигурацию, согласно правилам перехода.
Если автомат находилсяв конфигурации (q, σv, Zn . . . Z2 Z1 Z0 ) и δ(q, σ, z) = {(q1 , γ1 ), (q2 , γ2 )}, тоавтомат либо переходит в конфигурацию (q1 , v, γ1 Zn−1 . . . Z1 Z0 ), либо в(q2 , v, γ2 Zn−1 . . . Z1 Z0 ). Верхушка стека в цепочке γ ∈ Γ∗ находится слева,дно стека находится справа.На множестве конфигураций автомата P введено отношение `, такоеPчто если из конфигурации c1 согласно функции перехода P есть переход в конфигурацию c2 , то c1 ` c2 . Когда ясно о каком автомате идётPречь, мы будем опускать индекс отношения.
Так, (q, σv, Zn . . . Z2 Z1 Z0 ) `(q1 , v, γ1 Zn−1 . . . Z1 Z0 )Замечание 2. При выполнении такта работы, автомат всегда снимает симол с верхушки стека. Например, если изначально автомат находился в конфигурации (q0 , av, Z0 ) и перешёл в конфигурацию (q, v, aZ0 ),то правило, которое он применил выглядит как (q, aZ0 ) ∈ δ(q0 , a, Z0 ).Кстати, в отличие от грамматик, входной алфавит и алфавит стекамогут пересекаться. То есть, условие Σ ∩ Γ = ∅ не налагается.2под «в результате» понимается что после обработки слова w автомат оказалсяпуст. Если стек оказался пуст в процессе обработки слова, т.е. когда слово ешё небыло прочитано до конца, то это не означает, что слово было принято автоматом3Напомним, что транзитивным замыканием бинарного отношения Rназывается минимальное транзитивное бинарное отношение R∗ , содержащее R.
То есть, если (a, b) ∈ R и (b, c) ∈ R, то (a, c) ∈ R∗ , даже если(a, c) 6∈ R. Кроме того, отношение R∗ само по себе является транзитивным, то есть, если (a, b) ∈ R∗ и (b, c) ∈ R∗ , то и (a, c) ∈ R∗ .Определим условие приёма слова w автоматом P через транзитивное замыкание отношения `. Если автомат P является допускающимпо принимающему состоянию, то w ∈ L(P ) тогда и только тогда, когда(q0 , w, Z0 ) `∗ (q, ε, γ), где q ∈ F , γ ∈ Γ∗ . Если автомат P является допускающим по пустому магазину, то (q0 , w, Z0 ) `∗ (q, ε, ε), где q ∈ Q – необязательно принимающее состояние.1.2ПримерыГрафически магазинные автоматы задаются следующим образом: длякаждого правила δ(q, σ, Z) = (p, γ) на переходе из состояния q в состояниеp пишут σ, Z/γ.
Если автомат принимает слово по пустому магазину, топринято считать, что F = ∅.a, Z0 /aZ0 a, a/aab, a/εq0b, a/εq1ε, Z0 /εq2Данный автомат является допускающим по завершающему состоянию.a, Z0 /aZ0 a, a/aab, a/ε ε, Z0 /εq0b, a/εq1Данный автомат является допускающим по пустому стеку.Упражнение 1. Показать, что данные автоматы распознают язык L ={an bn | n > 0}.Определение 3. Магазинный автомат P является детерминированным,если множество δ(q, σ, Z) содержит не более одного правила ∀σ ∈ Σ, ∀Z ∈Γ. Если для некоторой буквы σ, δ(q, σ, Z) 6= ∅, то δ(q, ε, Z) = ∅.
То есть4все переходы в автомате P определены однозначно и в случае когда изпары q, Z есть ε-переход, то других переходов из данной пары нет.Упражнение 2. Показать, что автоматы, изображённые на диаграммах являются детерминированными.Классическим примером КС-языков являются языки Дика. А именно, языком типа Dn будем называть язык состоящий из правильных скобочных выражений c n типами скобок. Формально, язык Dn определённад размеченым алфавитом Σ = Σn ∪ Σ̄n – в Σn входят открывающиесяскобки, в Σ̄n закрывающиеся.
Определим языки Дика индуктивно.Определение 4. Язык Дика Dn задан грамматикой S → σi σ̄i | σi S σ̄i | SS,где i ∈ 1..n.Скобочным итогом i−го типа слова w, назовём число kwki = |w|σi −|w|σ̄i . Если w является првильным скобочным выражением, то для любого префикса p : w = ps и любого i 6 n справедливо kpki > 0 и kwki = 0.То есть,w ∈ Dn ⇒ ∀i 6 n, ∀k 6 |w|, kw[1, k]ki > 0, kwki = 0Упражнение 3. Показать, что обратное неверно.2Задачи1.
Пусть D2 – язык правильных скобочных выражений с двумя типами.Тогда L = D2 ∩ ([1 |[2 )∗ (1 ]|2 ])∗ . То есть, L – язык скобочных выраженийширины 1, то есть [1 [2 [1 1 ]2 ]1 ] ∈ L, а [1 [2 [1 1 ]2 ][2 2 ]1 ] 6∈ L . Построить МПавтомат, распознающий язык L∗ .2. Привести алгоритм построения МП-автомата P , допускающего позаключительному состоянию по МП-автомату N , допускающего по пустому стеку.
Привести алгоритм обратного построения по автомату P ,автомата N . Если в задаче 1 Вы построили N -автомат, постройте понему аналогичный P -автомат, если вы построили P -автомат, постройтепо нему аналогичный N -автомат. Если вы не можете придумать алгоритм, его можно прочитать в книге Хопкрофта-Мотвани-Ульмана, ноэто не означает, что надо его перетехивать.5Задача 3. Построить КС-грамматику, порождающую1) язык палиндромов L ⊆ {a, b}∗ , то есть L = {w | w = wR }. Например,палиндромами являются слова «ротор» и «казак».2) язык L̄.4. Построить КС-грамматику G, порождающую L или МП-автомат M ,распознающий L.1.
L = {ai bj ck | i = j ∨ i = k; i, j, k > 0}2∗. L = {w | w = uv ⇒ u 6= v}, то есть w ∈ L непредставимо в виде uu.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}
