Теоретический минимум 2009 (1131627), страница 2
Текст из файла (страница 2)
Верно и обратное — для любого регулярного языка можноСтр. 8 из 15построить распознающий его конечный автомат.Определение регулярной грамматикиРегулярные грамматики — праволинейные (A → w, A → wB, w ∈ T*), леволинейные(A → w, A → Bw, w ∈ T*).Сформулировать соотношение между языками,порождаемыми праволинейными грамматиками иязыками, допускаемыми КАДля любой праволинейной грамматики существует конечный автомат, проверяющийпорождаемый грамматикой язык.
Для любого конечного автомата существуетправолинейная грамматика, порождающая проверяемый конечным автоматом язык.Определение эквивалентных состояний ДКАОпределение различимых состояний ДКАОпределение контекстно-свободной грамматики безε-правилA → α, α ∈ (N ∪ T)+допускается S → ε, если S не входит ни в какую правую частьОпределение контекстно-свободной грамматикиA → α, α ∈ (N ∪ T)*Определение выводимости в грамматикеОпределим на множестве (N ∪ T)* грамматики G = (N, T, P, S) бинарное отношениевыводимости «⇒» следующим образом: если δ → γ ∈ P, то αδβ ⇒ αγβ для всех α, β∈ (N ∪ T)*. Если α1 ⇒ α 2, то α2 непосредственно выводима из α1.Если α ⇒k β (k ≥ 0), то существует последовательность шаговСтр.
9 из 15γ0 ⇒ γ1 ⇒ γ2 ⇒ … ⇒ γk − 1 ⇒ γkгде α = γ0 и β = γk. Последовательность цепочек γ0, γ1, γ2, …, γk − 1, γk в этом случаеназывается выводом β из α.Определение языка, порождаемого КС-грамматикойЯзыком, порождаемым грамматикой G = (N, T, P, S) (обозначается L(G)) называетсямножество всех цепочек терминалов, выводимых из аксиомы, то есть:L(G) = {w | w ∈ T*, S ⇒+ w}Определение сентенциальной формыСентенциальная форма — цепочка (состоящая, в общем случае, из терминалов инетерминалов), выводимая из аксиомы грамматикиОпределение однозначной КС-грамматикиКС грамматика называется однозначной или детерминированной, если всякаявыводимая терминальная цепочка имеет только одно дерево вывода (соотвественнотолько один левый и только один правый вывод).Определение неоднозначной КС-грамматикиКС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α⊂L(G), для которой может быть построено два или более различных деревьеввывода.Определение недетерминированного МП автоматаНедетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M =(Q, T, Г, D, q0, Z0, F), где1.
Q — конечное множество состояний, представляющее всевозможныесостояния управляющего устройства2. T — конечный входной алфавит3. Г — конечный алфавит магазинных символов4. D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечныхСтр. 10 из 15подмножеств Q × Г*, называемое функцией переходов5. q0 ∈Q — начальное состояние управляющего устройства6. Z0 ∈Г — символ, находящийся в магазине в начальный момент (начальныйсимвол магазина)7. F ⊆Q — множество заключительных состоянийОпределение детерминированного МП автоматаДетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q,T, Г, D, q0, Z0, F), где1. Q — конечное множество состояний, представляющее всевозможныесостояния управляющего устройства2. T — конечный входной алфавит3. Г — конечный алфавит магазинных символов4.
D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечныхподмножеств Q × Г*, называемое функцией переходов5. q0 ∈ Q — начальное состояние управляющего устройства6. Z0 ∈ Г — символ, находящийся в магазине в начальный момент (начальныйсимвол магазина)7. F ⊆Q — множество заключительных состоянийКроме того, должны выполняться следующие условия:1. Множество D(q, a, Z) содержит не более одного элемента для любых q ∈ Q,a ∈ T ∪ {ε}, Z0 ∈ Г2.
Если D(q, ε, Z) ≠ ∅, то D(q, a, Z) = ∅ для всех a ∈ TОпределение конфигурации МП автоматаКонфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q,w, u), гдеq ∈ Q — текущее состояние магазинного устройстваw ∈ T* — непрочитанная часть входной цепочки; первый символ цепочки wнаходится под входной головкой; если w = ε, то считается, что входная лентапрочитанаu ∈ Г* — содержимое магазина; самый левый символ цепочки u считаетсявершиной магазина; если u = ε, то магазин считается пустымСтр.
11 из 15Определение языка, допускаемого МП автоматомЦепочка w допускается МП автоматом, если (q0, w, Z0) * (q, ε, u) для некоторых q ∈ Fи u ∈ Г*. Язык, допускаемый МП-автоматом M — множество всех цепочек,допускаемых автоматом M.Определение недетерминированного МП автомата,допускающего опустошением магазинаЦепочка w допускается МП автоматом, если (q0, w, Z0) * (q, ε, ε) для некоторогоq ∈ Q.
В таком случае говорят, что автомат допускает цепочку опустошениеммагазина.Соотношение, между языками, порождаемымиКС-грамматиками, и языками, допускаемыминедетерминированными МП автоматамиОни совпадают.Формулировка леммы о разрастании для КС-языковДля любого контекстно-свободного языка L существуют такие целые l и k, что любаяцепочка α ∈ L, |α| > l представима в виде α = uvwxy, где1. |vwx| <= k2. vx != e3.
uviwxiy ∈ L для любого i >= 0Определение нормальной формы Хомского дляКС-грамматикиговорят что КС-грамматика находится в нормальной форме Холмского если каждоеправило имеет вид:1. Либо A → BC, A,B,C - нетерминалы2. либо A → α, α - терминал3. либо S → e, в таком случае S не встречается в правых частях правилСтр. 12 из 15Определение правостороннего вывода в КС-грамматикеВывод, в котором в любой сентенциальной форме на каждом шаге делаетсяподстановка самого правого нетерминала, называется правосторонним.Определение левостороннего вывода в КС-грамматикеВывод, в котором в любой сентенциальной форме на каждом шаге делаетсяподстановка самого левого нетерминала, называется левосторонним.Что такое леворекурсивная грамматика?Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой,что существует вывод A ⇒+ Au для некоторой строки u.Определение множества FIRST1FIRST1 — множество всех терминальных символов, с которых может начинатьсяцепочка терминальных символов, выводимых из цели грамматики или ε, если u ⇒* ε.Пример:* S → aS | A* A → b | bSd | bA | ε* FIRST1 = {a, b, ε}Определение множества FOLLOW1Определение LL(1) грамматикиLL(1)-грамматика - грамматика, для которой таблица предсказывающего анализаторане имеет неоднозначно определенных входовОпределение LR(1) ситуацииLR(1)-ситуацией называется пара [A → α .
β, a], где A → α β — правило грамматики,a — терминал или правый концевой маркер $. Вторая компонента ситуацииназывается аванцепочкой.Стр. 13 из 15Определение LR(1) грамматикиКакого типа конфликты могут появиться вканонической системе множеств LR(1) ситуаций?Shi -Reduce и Reduce-ReduceОпределение конфигурации LR-анализатораПара (Содержимое магазина, непросмотренный вход)Как меняется конфигурация LR-анализатора придействии reduce?Убрать из стека правую часть правила, добавить левую и состояние goto(последнеесостояние в магазине, символ из левой части правила)Какие типы действий выполняет LR-анализатор?Shi , Reduce, Accept, RejectКак меняется конфигурация LR-анализатора придействии shi ?Перенести верхний символ входа в магазин, занести наверх магазина состояниеac on(предыдущее состояние, взятый символ)Что такое основа правой сентенциальной формыКонструирование Компиляторов01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16КалендарьСтр.
14 из 15пн пн пн пн пнФевральМарт12 19 2605 12 19 26Апрель 02 09 16 23 30Май07 14 21 28Материалы к экзаменуПроведение экзамена | Определения | Теормин: 2007, 2009 | Алгоритмы решения задачПолучено с h p://esyr.nizm.ru/wiki/%D0%9A%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D0%BE%D0%B2%2C_%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D1%83%D0%BC_%282009%29Последнее изменение этой страницы: 09:08, 6 декабря 2009.Стр. 15 из 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
