Конструирование Компиляторов, 03 лекция (от 26 февраля)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1232 участника 212.227.82.218 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | [[Конструирование Компиляторов, 02 лекция (от 19 февраля)|Предыдущая лекция]] | [[Конструирование Компиляторов, 04 лекция (от 05 марта)|Следующая лекция]] |
- | + | ||
- | + | Пусть дана некая МТ, и мы строим грамматику. Грамматика строится следующим образом: | |
- | + | ||
+ | # A<sub>1</sub> → q<sub>0</sub>A<sub>2</sub> | ||
+ | # A<sub>2</sub> → [a, a]A<sub>2</sub>, a ∈ Σ | ||
+ | # A<sub>2</sub> → A<sub>3</sub> | ||
+ | # A<sub>3</sub> → [ε, B]A<sub>3</sub> | ||
+ | # A<sub>3</sub> → ε | ||
+ | # q[a, C] → [a, E], p, a ∈ Σ ∪ {e}, q ∈ Q, C ∈ Γ, D(q, C) = (P, E, R) | ||
+ | # [b, I]q[a, C] → p[b, I][a, J], C, I, J ∈ Γ, a, b ∈ Σ ∪ {e}, D(q, C) = (P, J, L) | ||
+ | # [a, C]q → qaq, q[a, C] → qaq, q → e, a ∈ Σ ∪ {e}, C ∈ Γ, q ∈ Γ | ||
+ | |||
+ | Некоторые нетерминалы имеют странноватый вид: [a, C]. Это всего лишь обозначения. Можно было придумать специальное имя, но это неважно. Это наименование несёт некий подсказывательный смысл. А<sub>1</sub> — аксиома. Из А<sub>1</sub> выводится q<sub>0</sub>. Из А<sub>2</sub> выводится некоторое количество пар [a1, a1][a2, a2]...[aL, aL]А<sub>2</sub>: | ||
+ | А<sub>1</sub> ⇒ q<sub>0</sub>А<sub>2</sub> ⇒* [a1, a1][a2, a2]...[an, an]А<sub>2</sub> ⇒ [a1, a1][a2, a2]...[an, an]А<sub>23</sub> ⇒* [a1, a1][a2, a2]...[an, an][e, B]<sup></sup> ⇒ | ||
+ | |||
+ | Далее применяем правило 6, когда головка сдвигается вправо, 7, когда влево. | ||
+ | |||
+ | Картинка: | ||
+ | {| | ||
+ | |a<sub>1</sub> | ||
+ | |... | ||
+ | |a<sub>n</sub> | ||
+ | |ε | ||
+ | |... | ||
+ | |ε | ||
+ | |- | ||
+ | |a<sub>1</sub> | ||
+ | |... | ||
+ | |a<sub>n</sub> | ||
+ | |B | ||
+ | |... | ||
+ | |B | ||
+ | |} | ||
+ | |||
+ | Если есть переход МТ: | ||
+ | * (q<sub>0</sub>, a<sub>1</sub>…a<sub>n</sub>, 1) |—* (q, x<sub>1</sub>…x<sub>s</sub>, r) | ||
+ | то есть вывод | ||
+ | * q<sub>0</sub>[a<sub>1</sub>, a<sub>1</sub>][a<sub>2</sub>, a<sub>2</sub>]…[a<sub>n</sub>, a<sub>n</sub>][e, B]<sup>m</sup> ⇒* [a<sub>1</sub>, x<sub>1</sub>][a<sub>2</sub>, x<sub>2</sub>]…[a<sub>r − 1</sub>, x<sub>r − 1</sub>]q[a<sub>r</sub>, xr]…[a<sub>n + m</sub>, x<sub>n + m</sub>] | ||
+ | |||
+ | {| | ||
+ | |a<sub>1</sub> | ||
+ | |a<sub>2</sub> | ||
+ | |... | ||
+ | |a<sub>i</sub> | ||
+ | |... | ||
+ | |a<sub>n</sub> | ||
+ | |ε | ||
+ | |colspan="2"|... | ||
+ | |ε | ||
+ | |- | ||
+ | |x<sub>1</sub> | ||
+ | |x<sub>2</sub> | ||
+ | |... | ||
+ | |x<sub>i</sub> | ||
+ | |colspan="2"|... | ||
+ | |xs | ||
+ | |B | ||
+ | |... | ||
+ | |B | ||
+ | |- | ||
+ | |colspan="4"| | ||
+ | |↑r | ||
+ | |} | ||
+ | |||
+ | Доказывается по индукции, ибо каждый шаг сохраняет это свойство. | ||
+ | |||
+ | Что такое m — ежели цепочка a1...an допускается МТ, то в конечном счёте МТ впадает в конечное состояние, и поскольку она дискретная, то она использует конечное количество ленты, и m — то дополнительное количество ячеек цепочки, которое использует МТ в процессе работы. | ||
+ | |||
+ | Что делает 8 правило: если q принадлежит F, то ликвидируем второй трек, и сводим слово к a1...an. И, следовательно, в грамматике будет выводить a1...an. | ||
+ | |||
+ | Обратно: так как грамматика порождает цепочки только из терминалов, то это значит, что мы получили финальное состояние, ибо терминальные цепочки порождаются только в нём. | ||
+ | |||
+ | Так как по МТ построили грамматику, по грамматике построили МТ, то если язык определяется грамматикой типа 0, то он же определяется с помощью распознавания МТ. | ||
+ | |||
+ | В этом доказательстве существенно используется то, что грамматика укорачивающая, и её нельзя отнести к 1 классу. | ||
+ | |||
+ | '''Определение'''. Языки типа 0 — рекурсивно перечислимые множества. | ||
+ | |||
+ | = Грамматики уровня 1 = | ||
+ | |||
+ | Определение. | ||
+ | |||
+ | Утверждение 1. Любой контекстно-чувствительный язык является рекурсивным. (рекурсивное множество — множество, определяемое алгоритмом). То есть, существует алгоритм (умеет останавливаться на любом входе). | ||
+ | |||
+ | '''Пример'''. Пусть грамматика G=(N,T,P,S) — неукорачивающая. Рассмотрим L(G). Утверждение: L(G) екурсивен. | ||
+ | |||
+ | Доказательство. Рассмотрим w ∈ T*, |w| = n. Если w = 0, то это ε. Мы проверяем, есть ли правило S → &epsilon. Пусть теперь w ≠ 0. Определим T<sub>m</sub> таких цепочек u ∈ (N ∪ T)<sub>+</sub>, что |u| ≤ n, S ⇒* m (длина вывода не превосходит m). Некое рекуррентное построение: T<sub>0</sub> = {S}. S попадает под наше определение. Поэтому теперь пишем рекуррентную формулу: T<sub>m</sub> = T<sub>m − 1</sub> ∪ {u | V →→ u, V ∈ T<sub>m − 1</sub>, |u| ≤ n}. Сколько может быть цепочек длины не больше n? Если можность алфавита |T ∪ N| = K, то число строк ограничено k<sup>n</sup>. Соответственно, найдётся такое m, что T<sub>m</sub> = T<sub>m − 1</sub>. Мы на этом можем остановиться, и поскольку мочность T<sub>m</sub> конечна, мы можем проверить, принадлежит ли w T<sub>m</sub>. Если принадлежит, то выводится, так как каждый элемент T<sub>m</sub> — сентенциальная форма, иначе не выводится. Это алгоритм. | ||
+ | |||
+ | <!-- педедыв --> | ||
+ | |||
+ | '''Определение'''. Линейно ограниченный автомат — машина Тьюринга, но такая МТ, что она если на вход подаётся цепочка a1...an, то вот эта МТ не использует в процессе своей работы ленту за пределами an. | ||
+ | |||
+ | '''Теорема'''. Язык является контекстно-чувствительным тогда и только тогда, когда он допускается линейно ограниченным автоматом. | ||
+ | |||
+ | '''Доказательство'''. В одну сторону: делаем второй трек, помещаем S и работаем. В другую сторону: в принципе доказательство точно такое же, единственная неприятность в том, что грамматика была укорачивающая из-за наличия q → ε. Надо исхитриться и обойтись без него. Граматика получается громоздкая, нро несложная, используя тот факт, что у нас есть два маркера. | ||
+ | |||
+ | Кто заинтересуется доказательством, есть книжка Мартыненко "Языки и трансляции", там грамматика приведена. | ||
+ | |||
+ | = Конечные автоматы и регулярные множества = | ||
+ | |||
+ | Рассмотрим лексический анализ (ЛА): принцип работы компилятор следующий: есть синтаксический анализ (СА), который периодически говорит "дай лексему", ЛА смотрит, выделяет лексему и возвращает СА символ. Обычно, ЛА это некая функция, которая вырабатывает некое значение (скалярный перечислимый тип). На Си это | ||
+ | |||
+ | int yylex() | ||
+ | { | ||
+ | ... | ||
+ | return v; | ||
+ | } | ||
+ | |||
+ | Кроме возвращения типа лексемы происходит некий побочный эффект — формируются таблицы, которые идут контекстному анализу, генерации кода... Поэтому основной задачей ЛА является выделение слов из потока. Наука, которая поддерживает этот процесс, называется конечные автоматы и регулярные выражения. | ||
+ | |||
+ | Мы будем рассматривать: | ||
+ | * Регулярные грамматики | ||
+ | * Регулярные выражения | ||
+ | * Конечные автоматы | ||
+ | |||
+ | '''Определение 1'''. Регулярное множество — пусть задан алфавит T. Регулярное множество определяется рекурсивно следующим образом: | ||
+ | * пустое множество является регулярным | ||
+ | * множество из {ε} является регулярным | ||
+ | * множество {a}, a ∈ T является регулярным | ||
+ | * Если есть P, Q — регулярные множества, то: | ||
+ | ** P ∪ Q является регулярным | ||
+ | ** PQ является регулярным | ||
+ | ** P* = ∪<sub>n = 0</sub><sup>∞</sup> P<sup>n</sup> является регулярным | ||
+ | * Больше ничто не является регулярным множеством | ||
+ | |||
+ | Обозначения: | ||
+ | * Пустое множество: ∅, {} | ||
+ | * ε | ||
+ | * a | ||
+ | * (p | q) | ||
+ | * (p.q) | ||
+ | *(p*) | ||
+ | |||
+ | Примеры, когда скобки можно опускать: | ||
+ | * (a|((ba)(a*))) → a|ba<sup>+</sup> | ||
+ | |||
+ | Алгебраические свойства: | ||
+ | * p|q = q|p | ||
+ | * ∅* = e | ||
+ | * p(q|r) = (p|q)|r = (p|q|r) | ||
+ | * p(qr) = (pq)r = pqr | ||
+ | * p(q|r) = pq|pr | ||
+ | * (p|q|r) = pr|qr | ||
+ | * pe = ep = p | ||
+ | * ∅p = p∅ = p | ||
+ | * p* = p|p* | ||
+ | * (p*)* = p* | ||
+ | * p|p = p | ||
+ | * p|∅ | ||
+ | |||
+ | Макроопределение: | ||
+ | * d1 = r1 | ||
+ | * d2 = r2 | ||
+ | * ... | ||
+ | * dk = rk | ||
+ | Ограничения: нельзя использовать неопределённые определения | ||
+ | |||
+ | Пример: | ||
+ | *digit = 0|1|...|9 | ||
+ | * letter = a|...|z|A|...|Z | ||
+ | * ident = letter(letter|digit)* | ||
+ | |||
+ | Пример с описанием паскалевского числа. | ||
+ | |||
+ | Некоторый алгоритм распознавания: конечный автоматом | ||
+ | |||
+ | КА — частная маленькая МТ, которая определяется следующим образом: | ||
+ | * M = (Q, T, D, q<sub>0</sub>, F) | ||
+ | * D: Q × (T ∪ {e}) → 2<sup>Q</sup> = {q1, q2, ...} | ||
+ | * q0 ∈ Q | ||
+ | * F <= Q | ||
+ | |||
+ | Есть лента, есть головка, есть функция управления D, которая делает следующую вещь: если автомат находится в состоянии q и читает символ t под головкой, то если опеределена пара (q, t), то автомат недетерминированно переходит в новое состояние. На самом деле, из этого автомата появляется набор новых автоматов, каждый из которых переходит в своё состояние, и они плодятся, плодятся, плодятся. Если функция определена на {q, e}, то автомат имеет право ничего не читать. Иногда КА будем изображать диаграммой переходов автоматов. Нарисовали кружочки для каждого состояния, и рисуем стрелки из состояния в состояния с символом a, если есть по a переход из первого состояния во второе. Кроме того, могут быть переходы по e, и по одному символу в два разных состояния. Если же D: Q × T → Q, то он детерминированный. | ||
+ | |||
+ | Конфигурация автомата — двойка (q, w). | ||
+ | |||
+ | Кроме того, КА не может писать и может двигаться только вперёд. | ||
+ | |||
+ | (q, aw) |— (p, w), D(q, a) &inis; P, a ∈ T ∪ {e} — такт автомата. Это бинарное отношение | ||
+ | |||
+ | Определяем рефлексивное, транзитивное замыкание отношения такта: |—* — существует последовательность конфигураций, которая приводит из левой части в правую. | ||
+ | |||
+ | Определяемый язык: | ||
+ | L(m) = {w|(q0, w) |—* (p, e), p ∈ F} | ||
+ | |||
+ | Вопросы: | ||
+ | * Эквивалентны ли НКА и ДКА | ||
+ | * Описывают ли РВ, КА одно и то же множество языков | ||
+ | |||
+ | Пример: Числа Паскаля: | ||
+ | (см. рисунок) | ||
+ | |||
+ | Теорема. Для всякого НКА существует эквивалентный ему ДКА. | ||
+ | |||
+ | * e-closure(R), r <= Q — множество состояний, в которые можно попасть из R оп эпсилон-переходам: S = ∪<sub>q ∈ R</sub> {p|(q,e) |—* (p, e)} | ||
+ | * move(R, a), R <= Q, a ∈ T — S = ∪<sub>q ∈ R</sub> {p|p ∈ D(q, a)} | ||
+ | |||
+ | Построение ДКА: | ||
+ | * НКА M = (Q, T, D, q0, F | ||
+ | * ДКА M'=(Q', T, D', q0', F') | ||
+ | |||
+ | # q0' = e_closure({q0}) | ||
+ | # Q = {q0', ..., qi'v, ...}, q0' — непомеченное, состояния помечены, если с ними мы что-то проделали | ||
+ | # Цикл: | ||
+ | while (R ∈ Q' && R — непомеченное) | ||
+ | { | ||
+ | пометить R; | ||
+ | for (∀a ∈ T) | ||
+ | { | ||
+ | S = e_closure(move(R, a)); | ||
+ | |||
+ | if (S ≠ Q) | ||
+ | if (S ∉ Q') | ||
+ | добавить S в Q' как непомеченный | ||
+ | |||
+ | D'(R, a) = S; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | Написано следующее — крутиться, пока во множестве Q' есть некое R непомеченное. | ||
+ | |||
+ | # Заключительное состояние — F' = {S|S ∈ Q', q ∈ S, q ∈ F} | ||
+ | |||
+ | В чём идея — берём НКА, у него есть две неприятности — одна неприятность в том, что есть эпсилон переходы, вторая неприятность в том, что он может по одному символу перейти в разные состояния. Переходы опред следующим образом: объединяем все состояния, в которые можно перейти по данному символу и делаем эпсилон-замыкание, и делаем туда переход. | ||
+ | |||
+ | Напишем простенький алгоритм получения эпсилон-замыкания. | ||
+ | # поместить все состояния из R с стек stack | ||
+ | # Цикл: | ||
+ | { | ||
+ | while (stack ≠ {}) | ||
+ | { пусть t — верхний элемент stack; | ||
+ | удалить t из stack; | ||
+ | for (u ∈ D(t, e)) | ||
+ | if (u ∉ ε_closure(R)) | ||
+ | добавить u к ε_closure(R) | ||
+ | поместить u в stack | ||
+ | } | ||
+ | return(e_closure); | ||
+ | } | ||
+ | |||
+ | |||
+ | Теорема. ДКА и НКА эквивалентны по мощности. | ||
+ | |||
+ | Доказательство. Определим: | ||
+ | * _DДКА = (q, a) = D(q, a) | ||
+ | * _DДКА = (q, wa) = D(_DДКА(q, a), a) | ||
+ | * _DНКА(q, ε) = ε_closure({q}), w = xa | ||
+ | * _DНКА(q, ε) = ∪<sub>i = 1</sub><sup>k</sup>ε_closure(DНКА(pi, a)) | ||
+ | |||
+ | формулировка теоремы: _DДКА(&epsilon_closure({q0})), w) = _DНКА(q0, w) | ||
+ | |||
+ | Предположение индукции: w = e, |w| = 0, _DНКА(q0, e) = q0 = e_closure({q0}), | ||
+ | Шаг индукции: w = ma, _DДКА(e_closure({q0}, m)) = _DНКА(q0, m) = {p1, ..., pk}, _DДКА({q0}, na = _DНКА(q0, na)) = ∪<sub>i = 1</sub><sup>k</sup>ε_closure(DНКА(pi, a)) | ||
+ | |||
+ | РВ ГЗ КА, РВ → КА | ||
+ | |||
+ | РВ строится при помощи ∅, e, a, ∪, ., *. | ||
+ | * ∅: → (s) ((f)) | ||
+ | * ε: → (s) →ε ((f)) | ||
+ | * ... ||ну задолбался я писать то, что было на семинаре | ||
+ | |||
+ | {{Конструирование Компиляторов}} | ||
+ | {{Lection-stub}} |
Текущая версия
Предыдущая лекция | Следующая лекция
Пусть дана некая МТ, и мы строим грамматику. Грамматика строится следующим образом:
- A1 → q0A2
- A2 → [a, a]A2, a ∈ Σ
- A2 → A3
- A3 → [ε, B]A3
- A3 → ε
- q[a, C] → [a, E], p, a ∈ Σ ∪ {e}, q ∈ Q, C ∈ Γ, D(q, C) = (P, E, R)
- [b, I]q[a, C] → p[b, I][a, J], C, I, J ∈ Γ, a, b ∈ Σ ∪ {e}, D(q, C) = (P, J, L)
- [a, C]q → qaq, q[a, C] → qaq, q → e, a ∈ Σ ∪ {e}, C ∈ Γ, q ∈ Γ
Некоторые нетерминалы имеют странноватый вид: [a, C]. Это всего лишь обозначения. Можно было придумать специальное имя, но это неважно. Это наименование несёт некий подсказывательный смысл. А1 — аксиома. Из А1 выводится q0. Из А2 выводится некоторое количество пар [a1, a1][a2, a2]...[aL, aL]А2: А1 ⇒ q0А2 ⇒* [a1, a1][a2, a2]...[an, an]А2 ⇒ [a1, a1][a2, a2]...[an, an]А23 ⇒* [a1, a1][a2, a2]...[an, an][e, B] ⇒
Далее применяем правило 6, когда головка сдвигается вправо, 7, когда влево.
Картинка:
a1 | ... | an | ε | ... | ε |
a1 | ... | an | B | ... | B |
Если есть переход МТ:
- (q0, a1…an, 1) |—* (q, x1…xs, r)
то есть вывод
- q0[a1, a1][a2, a2]…[an, an][e, B]m ⇒* [a1, x1][a2, x2]…[ar − 1, xr − 1]q[ar, xr]…[an + m, xn + m]
a1 | a2 | ... | ai | ... | an | ε | ... | ε | |
x1 | x2 | ... | xi | ... | xs | B | ... | B | |
↑r |
Доказывается по индукции, ибо каждый шаг сохраняет это свойство.
Что такое m — ежели цепочка a1...an допускается МТ, то в конечном счёте МТ впадает в конечное состояние, и поскольку она дискретная, то она использует конечное количество ленты, и m — то дополнительное количество ячеек цепочки, которое использует МТ в процессе работы.
Что делает 8 правило: если q принадлежит F, то ликвидируем второй трек, и сводим слово к a1...an. И, следовательно, в грамматике будет выводить a1...an.
Обратно: так как грамматика порождает цепочки только из терминалов, то это значит, что мы получили финальное состояние, ибо терминальные цепочки порождаются только в нём.
Так как по МТ построили грамматику, по грамматике построили МТ, то если язык определяется грамматикой типа 0, то он же определяется с помощью распознавания МТ.
В этом доказательстве существенно используется то, что грамматика укорачивающая, и её нельзя отнести к 1 классу.
Определение. Языки типа 0 — рекурсивно перечислимые множества.
[править] Грамматики уровня 1
Определение.
Утверждение 1. Любой контекстно-чувствительный язык является рекурсивным. (рекурсивное множество — множество, определяемое алгоритмом). То есть, существует алгоритм (умеет останавливаться на любом входе).
Пример. Пусть грамматика G=(N,T,P,S) — неукорачивающая. Рассмотрим L(G). Утверждение: L(G) екурсивен.
Доказательство. Рассмотрим w ∈ T*, |w| = n. Если w = 0, то это ε. Мы проверяем, есть ли правило S → &epsilon. Пусть теперь w ≠ 0. Определим Tm таких цепочек u ∈ (N ∪ T)+, что |u| ≤ n, S ⇒* m (длина вывода не превосходит m). Некое рекуррентное построение: T0 = {S}. S попадает под наше определение. Поэтому теперь пишем рекуррентную формулу: Tm = Tm − 1 ∪ {u | V →→ u, V ∈ Tm − 1, |u| ≤ n}. Сколько может быть цепочек длины не больше n? Если можность алфавита |T ∪ N| = K, то число строк ограничено kn. Соответственно, найдётся такое m, что Tm = Tm − 1. Мы на этом можем остановиться, и поскольку мочность Tm конечна, мы можем проверить, принадлежит ли w Tm. Если принадлежит, то выводится, так как каждый элемент Tm — сентенциальная форма, иначе не выводится. Это алгоритм.
Определение. Линейно ограниченный автомат — машина Тьюринга, но такая МТ, что она если на вход подаётся цепочка a1...an, то вот эта МТ не использует в процессе своей работы ленту за пределами an.
Теорема. Язык является контекстно-чувствительным тогда и только тогда, когда он допускается линейно ограниченным автоматом.
Доказательство. В одну сторону: делаем второй трек, помещаем S и работаем. В другую сторону: в принципе доказательство точно такое же, единственная неприятность в том, что грамматика была укорачивающая из-за наличия q → ε. Надо исхитриться и обойтись без него. Граматика получается громоздкая, нро несложная, используя тот факт, что у нас есть два маркера.
Кто заинтересуется доказательством, есть книжка Мартыненко "Языки и трансляции", там грамматика приведена.
[править] Конечные автоматы и регулярные множества
Рассмотрим лексический анализ (ЛА): принцип работы компилятор следующий: есть синтаксический анализ (СА), который периодически говорит "дай лексему", ЛА смотрит, выделяет лексему и возвращает СА символ. Обычно, ЛА это некая функция, которая вырабатывает некое значение (скалярный перечислимый тип). На Си это
int yylex() { ... return v; }
Кроме возвращения типа лексемы происходит некий побочный эффект — формируются таблицы, которые идут контекстному анализу, генерации кода... Поэтому основной задачей ЛА является выделение слов из потока. Наука, которая поддерживает этот процесс, называется конечные автоматы и регулярные выражения.
Мы будем рассматривать:
- Регулярные грамматики
- Регулярные выражения
- Конечные автоматы
Определение 1. Регулярное множество — пусть задан алфавит T. Регулярное множество определяется рекурсивно следующим образом:
- пустое множество является регулярным
- множество из {ε} является регулярным
- множество {a}, a ∈ T является регулярным
- Если есть P, Q — регулярные множества, то:
- P ∪ Q является регулярным
- PQ является регулярным
- P* = ∪n = 0∞ Pn является регулярным
- Больше ничто не является регулярным множеством
Обозначения:
- Пустое множество: ∅, {}
- ε
- a
- (p | q)
- (p.q)
- (p*)
Примеры, когда скобки можно опускать:
- (a|((ba)(a*))) → a|ba+
Алгебраические свойства:
- p|q = q|p
- ∅* = e
- p(q|r) = (p|q)|r = (p|q|r)
- p(qr) = (pq)r = pqr
- p(q|r) = pq|pr
- (p|q|r) = pr|qr
- pe = ep = p
- ∅p = p∅ = p
- p* = p|p*
- (p*)* = p*
- p|p = p
- p|∅
Макроопределение:
- d1 = r1
- d2 = r2
- ...
- dk = rk
Ограничения: нельзя использовать неопределённые определения
Пример:
- digit = 0|1|...|9
- letter = a|...|z|A|...|Z
- ident = letter(letter|digit)*
Пример с описанием паскалевского числа.
Некоторый алгоритм распознавания: конечный автоматом
КА — частная маленькая МТ, которая определяется следующим образом:
- M = (Q, T, D, q0, F)
- D: Q × (T ∪ {e}) → 2Q = {q1, q2, ...}
- q0 ∈ Q
- F <= Q
Есть лента, есть головка, есть функция управления D, которая делает следующую вещь: если автомат находится в состоянии q и читает символ t под головкой, то если опеределена пара (q, t), то автомат недетерминированно переходит в новое состояние. На самом деле, из этого автомата появляется набор новых автоматов, каждый из которых переходит в своё состояние, и они плодятся, плодятся, плодятся. Если функция определена на {q, e}, то автомат имеет право ничего не читать. Иногда КА будем изображать диаграммой переходов автоматов. Нарисовали кружочки для каждого состояния, и рисуем стрелки из состояния в состояния с символом a, если есть по a переход из первого состояния во второе. Кроме того, могут быть переходы по e, и по одному символу в два разных состояния. Если же D: Q × T → Q, то он детерминированный.
Конфигурация автомата — двойка (q, w).
Кроме того, КА не может писать и может двигаться только вперёд.
(q, aw) |— (p, w), D(q, a) &inis; P, a ∈ T ∪ {e} — такт автомата. Это бинарное отношение
Определяем рефлексивное, транзитивное замыкание отношения такта: |—* — существует последовательность конфигураций, которая приводит из левой части в правую.
Определяемый язык: L(m) = {w|(q0, w) |—* (p, e), p ∈ F}
Вопросы:
- Эквивалентны ли НКА и ДКА
- Описывают ли РВ, КА одно и то же множество языков
Пример: Числа Паскаля: (см. рисунок)
Теорема. Для всякого НКА существует эквивалентный ему ДКА.
- e-closure(R), r <= Q — множество состояний, в которые можно попасть из R оп эпсилон-переходам: S = ∪q ∈ R {p|(q,e) |—* (p, e)}
- move(R, a), R <= Q, a ∈ T — S = ∪q ∈ R {p|p ∈ D(q, a)}
Построение ДКА:
- НКА M = (Q, T, D, q0, F
- ДКА M'=(Q', T, D', q0', F')
- q0' = e_closure({q0})
- Q = {q0', ..., qi'v, ...}, q0' — непомеченное, состояния помечены, если с ними мы что-то проделали
- Цикл:
while (R ∈ Q' && R — непомеченное) { пометить R; for (∀a ∈ T) { S = e_closure(move(R, a)); if (S ≠ Q) if (S ∉ Q') добавить S в Q' как непомеченный D'(R, a) = S; } }
Написано следующее — крутиться, пока во множестве Q' есть некое R непомеченное.
- Заключительное состояние — F' = {S|S ∈ Q', q ∈ S, q ∈ F}
В чём идея — берём НКА, у него есть две неприятности — одна неприятность в том, что есть эпсилон переходы, вторая неприятность в том, что он может по одному символу перейти в разные состояния. Переходы опред следующим образом: объединяем все состояния, в которые можно перейти по данному символу и делаем эпсилон-замыкание, и делаем туда переход.
Напишем простенький алгоритм получения эпсилон-замыкания.
- поместить все состояния из R с стек stack
- Цикл:
{ while (stack ≠ {}) { пусть t — верхний элемент stack; удалить t из stack; for (u ∈ D(t, e)) if (u ∉ ε_closure(R)) добавить u к ε_closure(R) поместить u в stack } return(e_closure); }
Теорема. ДКА и НКА эквивалентны по мощности.
Доказательство. Определим:
- _DДКА = (q, a) = D(q, a)
- _DДКА = (q, wa) = D(_DДКА(q, a), a)
- _DНКА(q, ε) = ε_closure({q}), w = xa
- _DНКА(q, ε) = ∪i = 1kε_closure(DНКА(pi, a))
формулировка теоремы: _DДКА(&epsilon_closure({q0})), w) = _DНКА(q0, w)
Предположение индукции: w = e, |w| = 0, _DНКА(q0, e) = q0 = e_closure({q0}), Шаг индукции: w = ma, _DДКА(e_closure({q0}, m)) = _DНКА(q0, m) = {p1, ..., pk}, _DДКА({q0}, na = _DНКА(q0, na)) = ∪i = 1kε_closure(DНКА(pi, a))
РВ ГЗ КА, РВ → КА
РВ строится при помощи ∅, e, a, ∪, ., *.
- ∅: → (s) ((f))
- ε: → (s) →ε ((f))
- ... ||ну задолбался я писать то, что было на семинаре
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
Календарь
пн | пн | пн | пн | пн | |
Февраль
| 12 | 19 | 26 | ||
Март
| 05 | 12 | 19 | 26 | |
Апрель
| 02 | 09 | 16 | 23 | 30 |
Май
| 07 | 14 | 21 | 28 |
Материалы к экзамену
Проведение экзамена |
Определения |
Теормин: 2007, 2009, 2012 |
Алгоритмы решения задач