Конструирование Компиляторов, Теоретический минимум (2009)

Материал из eSyr's wiki.

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

см. также ответы на вопросы теоретического минимума 2007 года, список определений.

Содержание

1 Алфавит
2 Определение грамматики
3 Определение грамматик типа 0 по Хомскому
4 Определение грамматик типа 1 (неукорачивающих) по Хомскому
5 Грамматика типа 2 (Контекстно-свободная, КС) по Хомскому
6 Грамматика типа 3 (Праволинейная) по Хомскому
7 Определение детерминированной машины Тьюринга
8 Определение конфигурации машины Тьюринга
9 Определение языка, допускаемого машиной Тьюринга
10 Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга
11 Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга
12 Определение регулярного множества
13 Определение регулярного выражения
14 Определение праволинейной грамматики
15 Определение недетерминированного конечного автомата
16 Определение детерминированного конечного автомата
17 Объяснить разницу между недетерминированным и детерминированным конечным автоматом
18 Определение конфигурации конечного автомата
19 Определение языка, допускаемого конечным автоматом
20 Определение ε-замыкания для подмножества состояний НКА
21 Определение расширенной функции переходов для КА
22 Определение расширенной функции переходов для НКА
23 Определение расширенной функции переходов для ДКА
24 Определение функции firstpos для поддерева в дереве регулярного выражения
25 Определение функции lastpos для поддерева в дереве регулярного выражения
26 Определение функции followpos для позиций в дереве регулярного выражения
27 Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА
28 Определение регулярной грамматики
29 Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА
30 Определение эквивалентных состояний ДКА
31 Определение различимых состояний ДКА
32 Определение контекстно-свободной грамматики без ε-правил
33 Определение контекстно-свободной грамматики
34 Определение выводимости в грамматике
35 Определение языка, порождаемого КС-грамматикой
36 Определение сентенциальной формы
37 Определение однозначной КС-грамматики
38 Определение неоднозначной КС-грамматики
39 Определение недетерминированного МП автомата
40 Определение детерминированного МП автомата
41 Определение конфигурации МП автомата
42 Определение языка, допускаемого МП автоматом
43 Определение недетерминированного МП автомата, допускающего опустошением магазина
44 Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами
45 Формулировка леммы о разрастании для КС-языков
46 Определение нормальной формы Хомского для КС-грамматики
47 Определение правостороннего вывода в КС-грамматике
48 Определение левостороннего вывода в КС-грамматике
49 Что такое леворекурсивная грамматика?
50 Определение множества FIRST1
51 Определение множества FOLLOW1
52 Определение LL(1) грамматики
53 Определение LR(1) ситуации
54 Определение LR(1) грамматики
55 Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?
56 Определение конфигурации LR-анализатора
57 Как меняется конфигурация LR-анализатора при действии reduce?
58 Какие типы действий выполняет LR-анализатор?
59 Как меняется конфигурация LR-анализатора при действии shift?
60 Что такое основа правой сентенциальной формы

[править] Алфавит

Алфавит - конечное множество символов

[править] Определение грамматики

Грамматика $~G = (N,T,P,S)$ - четверка множеств, где

$~N$ - алфавит нетерминальных символов
$~T$ - алфавит терминальных символов, $N \cap T = \empty$ ;
$~P$ - множество правил вида $\alpha \rarr \beta, \alpha \in ( N \cup T)^*N(N \cup T)^*, \beta \in (N \cup T)^*$
$S \in N$ - начальный символ или аксиома грамматики

[править] Определение грамматик типа 0 по Хомскому

Если на грамматику $~G = (N, T, P, S)$ не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений.

[править] Определение грамматик типа 1 (неукорачивающих) по Хомскому

Если

Каждое правило грамматики, кроме $S \rarr \epsilon$ , имеет вид $\alpha \rarr \beta, |\alpha| \le |\beta|$
В том случае, когда $S \rarr \epsilon \in P$ , символ $~S$ не встречается в правых частях правил

то грамматику называют грамматикой типа 1, или неукорачивающей.

[править] Грамматика типа 2 (Контекстно-свободная, КС) по Хомскому

Грамматика типа 2 (Контекстно-свободная, КС) - грамматика, где каждое правило $p \in P$ имеет вид $A \rarr \alpha$ , где $A \in N, \alpha \in (N \cup T)^*$

[править] Грамматика типа 3 (Праволинейная) по Хомскому

Грамматика типа 3 (Праволинейная) - грамматика, где $\forall p \in P$ имеет вид либо $A \rarr xB$ , либо $A \rarr x$ , где $A,B \in N, x \in T^*$

[править] Определение детерминированной машины Тьюринга

Детерминированная машина Тьюринга — T_m = (Q, Г, Σ, D, q₀, F)

Q — конечное множество состояний
Г — конечное множество ленточных символов (конечный алфавит), один из которых называется пустым и обозначается обычно b
Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ)
D — правила перехода
- D: (Q\F) × Г → Q × Г × {L, R}
q₀ ∈ Q — начальное состояние
F ⊆ Q — множество конечных состояний

[править] Определение конфигурации машины Тьюринга

Конфигурацией машины Тьюринга называется тройка (q, w, i), где

q ∈ Q — состояние машины Тьюринга
w ∈ Г* —текущее содержимое занятого участка ленты, w = a₁ … a_n
i ∈ Z — положение головки машины Тьюринга

[править] Определение языка, допускаемого машиной Тьюринга

Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q₀, w, 1) может достигнуть через конечное число переходов состояния q ∈ F.

[править] Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга

Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0.

[править] Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга

Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает.

[править] Определение регулярного множества

Регулярное множество в алфавите T определяется следующим образом:

$\varnothing$ — регулярное множество в алфавите T
$~\{a\}$ — регулярное множество в алфавите T для каждого a ∈ T
$~\{\epsilon\}$ — регулярное множество в алфавите T
Если P и Q — регулярные множества в алфавите T, то регулярны множества
- $~P \cup Q$ (объединение)
- $~PQ$ (конкатенация, $\{ pq | p \in P, q \in Q\}$ )
- $~P^*$ (итерация: $P^* = \{\epsilon\} \cup P \cup PP \cup PPP \cup ...)$
Ничто другое не является регулярным множеством в алфавите T

[править] Определение регулярного выражения

Регулярное выражение — форма записи регулярного множества.

Регулярное выражение и обозначаемое им регулярное множество определяются следующим образом:

∅ — обозначает множество {}
ε — обозначает множество {ε}
a — обозначает множество {a}
Если РВ p и q обозначают множества P и Q соответственно, то:
- (p|q) обозначает P ∪ Q
- pq обозначает PQ
- (p*) обозначет P*
Ничто другое не является регулярным выражением в данном алфавите

[править] Определение праволинейной грамматики

Праволинейная грамматика или грамматика типа 3 по Хомскому — грамматика вида A → w, A → wB, w ∈ T*.

[править] Определение недетерминированного конечного автомата

Недетерминированный конечный автомат - M = (Q, Σ, D, q₀, F)

Q — конечное непустое множество состояний
Σ — входной алфавит
D — правила перехода
- Q × ( Σ ∪ {ε} ) → 2^Q
q₀ ∈ Q — начальное состояние
F ⊆ Q — множество конечных состояний

[править] Определение детерминированного конечного автомата

Детерминированный конечный автомат - M = (Q, Σ, D, q₀, F)

Q — конечное непустое множество состояний
Σ — конечный входной алфавит
D — правила перехода
- Q × Σ → Q
q₀ ∈ Q — начальное состояние
F ⊆ Q — множество конечных состояний

[править] Объяснить разницу между недетерминированным и детерминированным конечным автоматом

Недетерминированный конечный автомат является обобщением детерминированного. Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). В детерменированном автомате из одного состояния допускается не более одного перехода для каждого символа алфавита, в недетерменированном - произвольное количество. Кроме того, в НКА возможны эпсилон-переходы.

[править] Определение конфигурации конечного автомата

Пусть M = (Q, T, D, q₀, F) — НКА. Конфигурацией автомата M называется пара (q, ω) ∈ Q × T*, где q — текущее состояние управляющего устройства, а ω — цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа от неё.

[править] Определение языка, допускаемого конечным автоматом

Автомат M допускает цепочку ω, если (q₀, ω) ⊦* (q, ε) для некоторого q ∈ F. Языком, допускаемым автоматом M, называется множество входных цепочек,допускаемых автоматом M. То есть:

L(M) = {ω | ω ∈ T* и (q₀, ω) ⊦* (q, ε) для некоторого q ∈ F}

[править] Определение ε-замыкания для подмножества состояний НКА

ε-замыкание множества состояний R, R ⊆ Q — множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по ε, то есть множество

S = ⋃_q ∈ R {p | (q, ε) ⊦* (p, ε)}

[править] Определение расширенной функции переходов для КА

Расширенная функция переходов множества состояний R, R ⊆ Q по a — множество состояний НКА, в которые есть переход на входе a для состояний из R, то есть множество

S = ⋃_q ∈ R {p | p ∈ D(q, a)}

[править] Определение расширенной функции переходов для НКА

[править] Определение расширенной функции переходов для ДКА

[править] Определение функции firstpos для поддерева в дереве регулярного выражения

Функция firstpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной n. Построение:

узел n	firstpos(n)
ε	∅
i ≠ ε	{i}
u \| v	firstpos(u) ∪ firstpos(v)
u . v	if nullable(u) then firstpos(u) ∪ firstpos(v) else firstpos(u)
v*	firstpos(v)

[править] Определение функции lastpos для поддерева в дереве регулярного выражения

Функция lastpos(n) для каждого узла n узла синтаксического дерева регулярных выражений даёт множество позиций, которым соответствуют последние символы в цепочках, генерируемых подвыражениями с вершиной n. Построение lastpos(n):

узел n	lastpos(n)
ε	∅
i ≠ ε	{i}
u \| v	lastpos(u) ∪ lastpos(v)
u . v	if nullable(v) then lastpos(u) ∪ lastpos(v) else lastpos(v)
v*	lastpos(v)

[править] Определение функции followpos для позиций в дереве регулярного выражения

Функция followpos(i) для позиции i есть множество позиций j таких, что существует некоторая строка …cd…, входящая в язык, описываемый регулярным выражением, такая, что позиция i соответствует вхождению c, а позиция j — вхождению d.

[править] Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА

Любой конечный автомат распознает регулярное множество цепочек символов входного алфавита. Верно и обратное — для любого регулярного языка можно построить распознающий его конечный автомат.

[править] Определение регулярной грамматики

Регулярные грамматики — праволинейные (A → w, A → wB, w ∈ T*), леволинейные (A → w, A → Bw, w ∈ T*).

[править] Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА

Для любой праволинейной грамматики существует конечный автомат, проверяющий порождаемый грамматикой язык. Для любого конечного автомата существует праволинейная грамматика, порождающая проверяемый конечным автоматом язык.

[править] Определение эквивалентных состояний ДКА

Два состояния $q i$ и $q j$ называются эквивалентными ( $q i$ ~ $q j$ ), если $\forall z\in$ T* верно, что $D(q_i, z)\in T \Leftrightarrow D(q_j, z)\in T$

[править] Определение различимых состояний ДКА

[править] Определение контекстно-свободной грамматики без ε-правил

A → α, α ∈ (N ∪ T)⁺
допускается S → ε, если S не входит ни в какую правую часть

[править] Определение контекстно-свободной грамматики

A → α, α ∈ (N ∪ T)*

[править] Определение выводимости в грамматике

Определим на множестве (N ∪ T)* грамматики G = (N, T, P, S) бинарное отношение выводимости «⇒» следующим образом: если δ → γ ∈ P, то αδβ ⇒ αγβ для всех α, β ∈ (N ∪ T)*. Если α₁ ⇒ α₂, то α₂ непосредственно выводима из α₁.

Если α ⇒^k β (k ≥ 0), то существует последовательность шагов

γ₀ ⇒ γ₁ ⇒ γ₂ ⇒ … ⇒ γ_{k − 1} ⇒ γ_k

где α = γ₀ и β = γ_k. Последовательность цепочек γ₀, γ₁, γ₂, …, γ_{k − 1}, γ_k в этом случае называется выводом β из α.

[править] Определение языка, порождаемого КС-грамматикой

Языком, порождаемым грамматикой G = (N, T, P, S) (обозначается L(G)) называется множество всех цепочек терминалов, выводимых из аксиомы, то есть:

L(G) = {w | w ∈ T*, S ⇒⁺ w}

[править] Определение сентенциальной формы

Сентенциальная форма — цепочка над алфавитом $(T \cup N)^*$ , выводимая из аксиомы грамматики

[править] Определение однозначной КС-грамматики

КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод).

[править] Определение неоднозначной КС-грамматики

КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ⊂ L(G), для которой может быть построено два или более различных деревьев вывода.

[править] Определение недетерминированного МП автомата

Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q₀, Z₀, F), где

Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
T — конечный входной алфавит
Г — конечный алфавит магазинных символов
D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функцией переходов
q₀ ∈Q — начальное состояние управляющего устройства
Z₀ ∈Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)
F ⊆Q — множество заключительных состояний

[править] Определение детерминированного МП автомата

Детерминированный автомат с магазинной памятью (МП-автомат) — семёрка M = (Q, T, Г, D, q₀, Z₀, F), где

Q — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
T — конечный входной алфавит
Г — конечный алфавит магазинных символов
D — отображение множества Q × (T ∪ {ε}) × Г в множество всех конечных подмножеств Q × Г*, называемое функцией переходов
q₀ ∈ Q — начальное состояние управляющего устройства
Z₀ ∈ Г — символ, находящийся в магазине в начальный момент (начальный символ магазина)
F ⊆ Q — множество заключительных состояний

Кроме того, должны выполняться следующие условия:

Множество D(q, a, Z) содержит не более одного элемента для любых q ∈ Q, a ∈ T ∪ {ε}, Z₀ ∈ Г
Если D(q, ε, Z) ≠ ∅, то D(q, a, Z) = ∅ для всех a ∈ T

[править] Определение конфигурации МП автомата

Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (q, w, u), где

q ∈ Q — текущее состояние магазинного устройства
w ∈ T* — непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = ε, то считается, что входная лента прочитана
u ∈ Г* — содержимое магазина; самый левый символ цепочки u считается вершиной магазина; если u = ε, то магазин считается пустым

[править] Определение языка, допускаемого МП автоматом

Цепочка w допускается МП автоматом, если (q₀, w, Z₀)⊢* (q, ε, u) для некоторых q ∈ F и u ∈ Г*. Язык, допускаемый МП-автоматом M — множество всех цепочек, допускаемых автоматом M.

[править] Определение недетерминированного МП автомата, допускающего опустошением магазина

Цепочка w допускается МП автоматом, если (q₀, w, Z₀)⊢* (q, ε, ε) для некоторого q ∈ Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина.

[править] Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами

Они совпадают.

[править] Формулировка леммы о разрастании для КС-языков

Для любого контекстно-свободного языка L существуют такие целые l и k, что любая цепочка α ∈ L, |α| > l представима в виде α = uvwxy, где

|vwx| <= k
vx != e
uvⁱwxⁱy ∈ L для любого i >= 0

[править] Определение нормальной формы Хомского для КС-грамматики

говорят что КС-грамматика находится в нормальной форме Хомского если каждое правило имеет вид:

Либо A → BC, A,B,C - нетерминалы
либо A → α, α - терминал
либо S → e, в таком случае S не встречается в правых частях правил

[править] Определение правостороннего вывода в КС-грамматике

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого нетерминала, называется правосторонним.

[править] Определение левостороннего вывода в КС-грамматике

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним.

[править] Что такое леворекурсивная грамматика?

Грамматика называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A ⇒⁺ Au для некоторой строки u.

[править] Определение множества FIRST1

FIRST1 — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или ε, если u ⇒* ε.

Пример:

   * S → aS | A
   * A → b | bSd | bA | ε
   * FIRST1 = {a, b, ε}

[править] Определение множества FOLLOW1

[править] Определение LL(1) грамматики

LL(1)-грамматика - грамматика, для которой таблица предсказывающего анализатора не имеет неоднозначно определенных входов

[править] Определение LR(1) ситуации

LR(1)-ситуацией называется пара [A → α . β, a], где A → α β — правило грамматики, a — терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

[править] Определение LR(1) грамматики

Грамматика называется LR(1), если из условий

1. $S' = > r u A w = > r u v w$ ,

2. $S' = > r z B x = > r u v y$ ,

3. FIRST(w) = FIRST(y)

следует, что uAy = zBx (т.е. u = z, A = B и x = y).

[править] Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?

Shift-Reduce и Reduce-Reduce

[править] Определение конфигурации LR-анализатора

Пара (Содержимое магазина, непросмотренный вход)

[править] Как меняется конфигурация LR-анализатора при действии reduce?

Убрать из стека правую часть правила, добавить левую и состояние goto(последнее состояние в магазине, символ из левой части правила)

[править] Какие типы действий выполняет LR-анализатор?

Shift, Reduce, Accept, Reject

[править] Как меняется конфигурация LR-анализатора при действии shift?

Перенести верхний символ входа в магазин, занести наверх магазина состояние action(предыдущее состояние, взятый символ)

[править] Что такое основа правой сентенциальной формы

Основа правой сентенциальной формы z - это правило вывода $A - > v$ и позиция в z, в которой может быть найдена цепочка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если $S = > r a v b$ , то $A - > v$ в позиции, следующей за a - это основа цепочки $a v b$ . Подцепочка b справа от основы содержит только терминальные символы.

Конструирование Компиляторов

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 | Алгоритмы решения задач

Получено с http://esyr.us/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

@@ Строка 1: / Строка 1: @@
 ''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].''
+== Алфавит ==
-# Определение грамматик типа 0 по Хомскому
+Алфавит - конечное множество символов
-# Определение грамматик типа 1 (неукорачивающих) по Хомскому
-# Определение детерминированной машины Тьюринга
+== Определение грамматики ==
-# Определение недетерминированной машины Тьюринга
+Грамматика <math>~G = (N,T,P,S)</math> - четверка множеств, где
-# Определение конфигурации машины Тьюринга
+* <math>~N</math> - алфавит нетерминальных символов
-# Определение языка, допускаемого машиной Тьюринга
+* <math>~T</math> - алфавит терминальных символов,  <math>N \cap T = \empty</math>;
-# Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга
+* <math>~P</math> - множество правил вида <math>\alpha \rarr \beta, \alpha \in ( N \cup T)^*N(N \cup T)^*, \beta \in (N \cup T)^*</math>
-# Объяснить разницу между недетерминированной и  детерминированной машиной Тьюринга
+* <math>S \in N</math> - начальный символ или аксиома грамматики
-# Определение регулярного множества
-# Определение регулярного выражения
+== Определение грамматик типа 0 по Хомскому ==
-# Определение праволинейной грамматики
+Если на грамматику <math>~G = (N, T, P, S)</math> не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений.
-# Определение недетерминированного конечного автомата
-# Определение детерминированного конечного автомата
+== Определение грамматик типа 1 (неукорачивающих) по Хомскому ==
-# Объяснить разницу между недетерминированным и  детерминированным конечным автоматом
+Если
-# Определение конфигурации конечного автомата
+# Каждое правило грамматики, кроме <math>S \rarr \epsilon </math> , имеет вид <math>\alpha \rarr \beta, |\alpha| \le |\beta|</math>
-# Определение языка, допускаемого конечным автоматом
+# В том случае, когда <math>S \rarr \epsilon \in P</math>, символ <math>~S</math> не встречается в правых частях правил
-# Определение &epsilon;-замыкания для подмножества состояний НКА
+то грамматику называют грамматикой типа 1, или неукорачивающей.
-# Определение расширенной функции переходов для ДКА
-# Определение расширенной функции переходов для НКА
+== Грамматика типа 2 (Контекстно-свободная, КС) по Хомскому ==
-# Определение функции firstpos для поддерева в дереве регулярного выражения
-# Определение функции lastpos для поддерева в дереве регулярного выражения
+Грамматика типа 2 (Контекстно-свободная, КС) - грамматика, где каждое правило <math>p \in P</math> имеет вид <math>A \rarr \alpha</math>, где <math> A \in N, \alpha \in (N \cup T)^*</math>
-# Определение функции followpos для позиций в дереве регулярного выражения
-# Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА
+== Грамматика типа 3 (Праволинейная) по Хомскому ==
-# Определение регулярной грамматики
-# Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА
+Грамматика типа 3 (Праволинейная) - грамматика, где <math> \forall p \in P </math> имеет вид либо <math> A \rarr xB </math>, либо <math> A \rarr x </math>, где <math> A,B \in N, x \in T^* </math>
-# Определение эквивалентных состояний ДКА
-# Определение различимых состояний ДКА
+== Определение детерминированной машины Тьюринга ==
-# Определение контекстно-свободной грамматики без е-правил
+'''Детерминированная машина Тьюринга''' — T<sub>m</sub> = (Q, Г, &Sigma;, D, q<sub>0</sub>, F)
-# Определение контекстно-свободной грамматики
+* Q — конечное множество состояний
-# Определение вывода в КС-грамматике
+* Г — конечное множество ленточных символов (конечный алфавит), один из которых называется пустым и обозначается обычно b
-# Определение языка, порождаемого КС-грамматикой
+* &Sigma; — входной алфавит, &Sigma; &sube; Г\{b}  (b - пустой символ)
-# Определение сентенциальной формы
+* D — правила перехода
-# Определение однозначной КС-грамматики
+** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R}
-# Определение неоднозначной КС-грамматики
+* q<sub>0</sub> &isin; Q — начальное состояние
-# Определение недетерминированного МП автомата
+* F &sube; Q — множество конечных состояний
-# Определение детерминированного МП автомата
-# Определение конфигурации МП автомата
-# Определение языка, допускаемого МП автоматом
-# Что означает то, что недетерминированный МП автомат допускает опустошением магазина
+== Определение конфигурации машины Тьюринга ==
-# Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами
+Конфигурацией машины Тьюринга называется тройка (q, w, i), где
-# Формулировка леммы о разрастании для КС-языков
+* q &isin; Q — состояние машины Тьюринга
-# Определение нормальной формы Хомского для КС-грамматики
+* w &isin; Г* —текущее содержимое занятого участка ленты, w = a<sub>1</sub> &hellip; a<sub>n</sub>
-# Определение правостороннего вывода в КС-грамматике
+* i &isin; Z — положение головки машины Тьюринга
-# Определение левостороннего вывода в КС-граммати
-# Какая грамматика называется леворекурсивной?
+== Определение языка, допускаемого машиной Тьюринга ==
-# Определение множества FIRST1
+Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q<sub>0</sub>, w, 1) может достигнуть через конечное число переходов состояния q &isin; F.
-# Определение множества FOLLOW1
-# Определение LL(1) Грамматики
+== Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга ==
-# Определение LR(1) ситуации
+Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0.
-# Определение LR(1) грамматики
-# Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций?
+== Объяснить разницу между недетерминированной и  детерминированной машиной Тьюринга ==
-# Определение конфигурации LR-анализатора
+Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает.
-# Как меняется конфигурация LR-анализатора при действии reduce?
-# Какие типы действий выполняет LR-анализатор?
+== Определение регулярного множества ==
-# Как меняется конфигурация LR-анализатора при действии shift?
-# Что такое основа правой сентенциальной формы
+'''Регулярное множество''' в алфавите T определяется следующим образом:
+* <math> \varnothing </math> — регулярное множество в алфавите T
+* <math> ~\{a\} </math> — регулярное множество в алфавите T для каждого a &isin; T
+* <math> ~\{\epsilon\} </math> — регулярное множество в алфавите T
+* Если P и Q — регулярные множества в алфавите T, то регулярны множества
+** <math>~P \cup Q</math> (объединение)
+** <math>~PQ</math> (конкатенация, <math>\{ pq | p \in P, q \in Q\}</math>)
+** <math>~P^*</math> (итерация: <math>P^* = \{\epsilon\} \cup P \cup PP \cup PPP \cup ...)</math>
+* Ничто другое не является регулярным множеством в алфавите T
+==  Определение регулярного выражения ==
+'''Регулярное выражение''' — форма записи [[Конструирование Компиляторов, Определения#Регулярное монжество|регулярного множества]].
+Регулярное выражение и обозначаемое им регулярное множество определяются следующим образом:
+* &empty; — обозначает множество {}
+* &epsilon; — обозначает множество {&epsilon;}
+* ''a'' — обозначает множество {''a''}
+* Если РВ ''p'' и ''q'' обозначают множества ''P'' и ''Q'' соответственно, то:
+** (''p''|''q'') обозначает ''P'' &cup; ''Q''
+** ''pq'' обозначает ''PQ''
+** (''p''*) обозначет ''P''*
+* Ничто другое не является регулярным выражением в данном алфавите
+== Определение праволинейной грамматики ==
+Праволинейная грамматика или грамматика типа 3 по Хомскому — грамматика вида A &rarr; w, A &rarr; wB, w &isin; T*.
+== Определение недетерминированного конечного автомата ==
+'''Недетерминированный конечный автомат''' - M = (Q, &Sigma;, D, q<sub>0</sub>, F)
+* Q — конечное непустое множество состояний
+* &Sigma; — входной алфавит
+* D — правила перехода
+** Q &times; ( &Sigma; &cup; {&epsilon;} ) &rarr; 2<sup>Q</sup>
+* q<sub>0</sub> &isin; Q — начальное состояние
+* F &sube; Q — множество конечных состояний
+<!-- про epsilon - моя отсебятина, его обычно потом отдельно добавляют -->
+<!-- или от нас требуется только нестрогое определение? -->
+== Определение детерминированного конечного автомата ==
+'''Детерминированный конечный автомат''' - M = (Q, &Sigma;, D, q<sub>0</sub>, F)
+* Q — конечное непустое множество состояний
+* &Sigma; — конечный входной алфавит
+* D — правила перехода
+** Q &times; &Sigma; &rarr; Q
+* q<sub>0</sub> &isin; Q — начальное состояние
+* F &sube; Q — множество конечных состояний
+<!-- или от нас требуется только нестрогое определение? -->
+== Объяснить разницу между недетерминированным и  детерминированным конечным автоматом ==
+Недетерминированный конечный автомат является обобщением детерминированного. Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными).
+В детерменированном автомате из одного состояния допускается не более одного перехода для каждого символа алфавита, в недетерменированном - произвольное количество. Кроме того, в НКА возможны эпсилон-переходы.
+== Определение конфигурации конечного автомата ==
+Пусть ''M'' = (''Q'', ''T'', ''D'', ''q''<sub>0</sub>, ''F'') — НКА. Конфигурацией автомата ''M'' называется пара (''q'', &omega;)&nbsp;&isin;&nbsp;''Q''&nbsp;&times;&nbsp;''T''*, где ''q''&nbsp;— текущее состояние управляющего устройства, а &omega;&nbsp;— цепочка символов на входной ленте, состоящая из символов под головкой и всех символов справа от неё.
+== Определение языка, допускаемого конечным автоматом ==
+Автомат ''M'' допускает цепочку &omega;, если (''q''<sub>0</sub>, &omega;)&nbsp;⊦*&nbsp;(''q'',&nbsp;&epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''F''. Языком, допускаемым автоматом ''M'', называется множество входных цепочек,допускаемых автоматом ''M''. То есть:
+* ''L(M)'' = {&omega; | &omega; &isin; ''T''* и (''q''<sub>0</sub>, &omega;)&nbsp;⊦*&nbsp;(''q'',&nbsp;&epsilon;)'' для некоторого ''q''&nbsp;&isin;&nbsp;''F''}
+== Определение &epsilon;-замыкания для подмножества состояний НКА ==
+&epsilon;-замыкание множества состояний ''R'', ''R''&nbsp;&sube;&nbsp;''Q''&nbsp;— множество состояний НКА, достижимых из состояний, входящих в ''R'', посредством только переходов по &epsilon;, то есть множество
+* S&nbsp;=&nbsp;⋃<sub>q&nbsp;&isin;&nbsp;R</sub>&nbsp;{p&nbsp;| (q,&nbsp;&epsilon;)&nbsp;⊦*&nbsp;(p,&nbsp;&epsilon;)}
+== Определение расширенной функции переходов для КА ==
+<!-- не для НКА ли это определение? -->
+Расширенная функция переходов множества состояний ''R'', ''R''&nbsp;&sube;&nbsp;''Q'' по ''a''&nbsp;— множество состояний НКА, в которые есть переход на входе ''a'' для состояний из ''R'', то есть множество
+* S&nbsp;=&nbsp;⋃<sub>q&nbsp;&isin;&nbsp;R</sub>&nbsp;{p&nbsp;| p&nbsp;&isin;&nbsp;D(q,&nbsp;a)}
+== Определение расширенной функции переходов для НКА ==
+== Определение расширенной функции переходов для ДКА ==
+== Определение функции firstpos для поддерева в дереве регулярного выражения ==
+Функция ''firstpos(n)'' для каждого узла ''n'' узла синтаксического дерева регулярных выражений даёт множество позиций, которые соответствуют первым символам в цепочках, генерируемых подвыражением с вершиной ''n''. Построение:
+{|
+ !узел ''n''
+ !''firstpos(n)''
+ |-
+ |&epsilon;
+ |&empty;
+ |-
+ |''i''&nbsp;&ne;&nbsp;&epsilon;
+ |{''i''}
+ |-
+ |u &#124; v
+ |''firstpos''(''u'')&nbsp;&cup;&nbsp;''firstpos''(''v'')
+ |-
+ |u . v
+ |if ''nullable''(''u'') then ''firstpos''(''u'')&nbsp;&cup;&nbsp;''firstpos''(''v'') else ''firstpos''(''u'')
+ |-
+ |v*
+ |''firstpos''(''v'')
+ |}
+== Определение функции lastpos для поддерева в дереве регулярного выражения ==
+Функция ''lastpos(n)'' для каждого узла ''n'' узла синтаксического дерева регулярных выражений даёт множество позиций, которым соответствуют последние символы в цепочках, генерируемых подвыражениями с вершиной ''n''.
+Построение ''lastpos''(''n''):
+{|
+ !узел ''n''
+ !''lastpos(n)''
+ |-
+ |&epsilon;
+ |&empty;
+ |-
+ |''i''&nbsp;&ne;&nbsp;&epsilon;
+ |{''i''}
+ |-
+ |u &#124; v
+ |''lastpos''(''u'')&nbsp;&cup;&nbsp;''lastpos''(''v'')
+ |-
+ |u . v
+ |if ''nullable''(''v'') then ''lastpos''(''u'')&nbsp;&cup;&nbsp;''lastpos''(''v'') else ''lastpos''(''v'')
+ |-
+ |v*
+ |''lastpos''(''v'')
+ |}
+== Определение функции followpos для позиций в дереве регулярного выражения ==
+Функция ''followpos(i)'' для позиции ''i'' есть множество позиций ''j'' таких, что существует некоторая строка ''&hellip;cd&hellip;'', входящая в язык, описываемый регулярным выражением, такая, что позиция ''i'' соответствует вхождению ''c'', а позиция ''j''&nbsp;— вхождению ''d''.
+== Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА ==
+Любой конечный автомат распознает регулярное множество цепочек символов входного алфавита.
+Верно и обратное&nbsp;— для любого регулярного языка можно построить распознающий его конечный автомат.
+== Определение регулярной грамматики ==
+Регулярные грамматики — праволинейные (A &rarr; w, A &rarr; wB, w &isin; T*), леволинейные (A &rarr; w, A &rarr; Bw, w &isin; T*).
+== Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА ==
+Для любой праволинейной грамматики существует конечный автомат, проверяющий порождаемый грамматикой язык. Для любого конечного автомата существует праволинейная грамматика, порождающая проверяемый конечным автоматом язык.
+== Определение эквивалентных состояний ДКА ==
+Два состояния <math>q_i</math> и <math>q_j</math> называются эквивалентными (<math>q_i</math> ~ <math>q_j</math>), если <math>\forall z\in</math> T* верно, что <math>D(q_i, z)\in T \Leftrightarrow D(q_j, z)\in T</math>
+== Определение различимых состояний ДКА ==
+== Определение контекстно-свободной грамматики без &epsilon;-правил ==
+* A &rarr; &alpha;, &alpha; &isin; (N &cup; T)<sup>+</sup>
+* допускается S &rarr; &epsilon;, если S не входит ни в какую правую часть
+== Определение контекстно-свободной грамматики ==
+A &rarr; &alpha;, &alpha; &isin; (N &cup; T)*
+== Определение выводимости в грамматике ==
+Определим на множестве (''N'' &cup; ''T'')* грамматики ''G'' = (''N'', ''T'', ''P'', ''S'') бинарное отношение выводимости «&rArr;» следующим образом: если ''&delta;'' &rarr; ''&gamma;'' &isin; ''P'', то ''&alpha;&delta;&beta;'' &rArr; ''&alpha;&gamma;&beta;'' для всех ''&alpha;'', ''&beta;'' &isin; (''N'' &cup; ''T'')*. Если ''&alpha;''<sub>1</sub> &rArr; ''&alpha;''<sub>2</sub>, то ''&alpha;''<sub>2</sub> непосредственно выводима из ''&alpha;''<sub>1</sub>.
+Если ''&alpha;'' &rArr;<sup>''k''</sup> ''&beta;'' (''k'' &ge; 0), то существует последовательность шагов
+* ''&gamma;''<sub>0</sub> &rArr; ''&gamma;''<sub>1</sub> &rArr; ''&gamma;''<sub>2</sub> &rArr; &hellip; &rArr; ''&gamma;''<sub>''k'' &minus; 1</sub> &rArr; ''&gamma;''<sub>''k''</sub>
+где ''&alpha;'' = ''&gamma;''<sub>0</sub> и ''&beta;'' = ''&gamma;''<sub>''k''</sub>. Последовательность цепочек ''&gamma;''<sub>0</sub>, ''&gamma;''<sub>1</sub>, ''&gamma;''<sub>2</sub>, &hellip;, ''&gamma;''<sub>''k'' &minus; 1</sub>, ''&gamma;''<sub>''k''</sub> в этом случае называется выводом ''&beta;'' из ''&alpha;''.
+== Определение языка, порождаемого КС-грамматикой ==
+Языком, порождаемым грамматикой ''G'' = (''N'', ''T'', ''P'', ''S'') (обозначается ''L''(''G'')) называется множество всех цепочек терминалов, выводимых из аксиомы, то есть:
+* ''L''(''G'') = {''w'' | ''w'' &isin; ''T''*, ''S'' &rArr;<sup>+</sup> ''w''}
+== Определение сентенциальной формы ==
+'''Сентенциальная форма''' — цепочка над алфавитом <math> (T \cup N)^* </math>, выводимая из аксиомы грамматики
+== Определение однозначной КС-грамматики ==
+КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод).
+== Определение неоднозначной КС-грамматики ==
+КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ⊂ L(G), для которой может быть построено два или более различных деревьев вывода.
+== Определение недетерминированного МП автомата ==
+Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''M'' = (''Q'', ''T'', ''Г'', ''D'', ''q''<sub>0</sub>, ''Z''<sub>0</sub>, ''F''), где
+# ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
+# ''T'' — конечный входной алфавит
+# ''Г'' — конечный алфавит магазинных символов
+# ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов
+# ''q''<sub>0</sub>&nbsp;&isin;''Q'' — начальное состояние управляющего устройства
+# ''Z''<sub>0</sub>&nbsp;&isin;''Г'' — символ, находящийся в магазине в начальный момент (начальный символ магазина)
+# ''F''&nbsp;&sube;''Q'' — множество заключительных состояний
+== Определение детерминированного МП автомата ==
+Детерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''M'' = (''Q'', ''T'', ''Г'', ''D'', ''q''<sub>0</sub>, ''Z''<sub>0</sub>, ''F''), где
+# ''Q'' — конечное множество состояний, представляющее всевозможные состояния управляющего устройства
+# ''T'' — конечный входной алфавит
+# ''Г'' — конечный алфавит магазинных символов
+# ''D'' — отображение множества ''Q'' &times; (''T'' &cup; {&epsilon;}) &times; ''Г'' в множество всех конечных подмножеств ''Q''&nbsp;&times;&nbsp;''Г''*, называемое функцией переходов
+# ''q''<sub>0</sub>&nbsp;&isin;&nbsp;''Q'' — начальное состояние управляющего устройства
+# ''Z''<sub>0</sub>&nbsp;&isin;&nbsp;''Г'' — символ, находящийся в магазине в начальный момент (начальный символ магазина)
+# ''F''&nbsp;&sube;&nbsp;''Q'' — множество заключительных состояний
+Кроме того, должны выполняться следующие условия:
+# Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q''&nbsp;&isin;&nbsp;''Q'', ''a''&nbsp;&isin;&nbsp;''T'' &cup; {&epsilon;}, ''Z''<sub>0</sub>&nbsp;&isin;&nbsp;''Г''
+# Если ''D''(''q'', &epsilon;, ''Z'') &ne; &empty;, то ''D''(''q'', ''a'', ''Z'') = &empty; для всех ''a''&nbsp;&isin;&nbsp;''T''
+== Определение конфигурации МП автомата ==
+Конфигурацией автомата с магазинной памятью (МП автомата) называется тройка (''q'', ''w'', ''u''), где
+* ''q''&nbsp;&isin;&nbsp;''Q'' — текущее состояние магазинного устройства
+* ''w''&nbsp;&isin;&nbsp;''T''* — непрочитанная часть входной цепочки; первый символ цепочки ''w'' находится под входной головкой; если ''w'' = &epsilon;, то считается, что входная лента прочитана
+* ''u''&nbsp;&isin;&nbsp;''Г''* — содержимое магазина; самый левый символ цепочки ''u'' считается вершиной магазина; если ''u = &epsilon;, то магазин считается пустым
+== Определение языка, допускаемого МП автоматом ==
+Цепочка ''w'' допускается МП автоматом, если (''q''<sub>0</sub>, ''w'', ''Z''<sub>0</sub>)⊢* (''q'', &epsilon;, ''u'') для некоторых ''q''&nbsp;&isin;&nbsp;''F'' и ''u''&nbsp;&isin;&nbsp;''Г''*. Язык, допускаемый МП-автоматом ''M'' — множество всех цепочек, допускаемых автоматом ''M''.
+== Определение недетерминированного МП автомата, допускающего опустошением магазина ==
+Цепочка ''w'' допускается МП автоматом, если (''q''<sub>0</sub>, ''w'', ''Z''<sub>0</sub>)⊢* (''q'', &epsilon;, &epsilon;) для некоторого ''q''&nbsp;&isin;&nbsp;''Q''. В таком случае говорят, что автомат допускает цепочку ''опустошением магазина''.
+== Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами ==
+Они совпадают.
+== Формулировка леммы о разрастании для КС-языков ==
+Для любого контекстно-свободного языка L существуют такие целые l и k, что любая цепочка &alpha; &isin; L, |&alpha;| >  l представима в виде &alpha; = uvwxy, где
+# |vwx| <= k
+# vx != e
+# uv<sup>i</sup>wx<sup>i</sup>y &isin; L для любого i >= 0
+== Определение нормальной формы Хомского для КС-грамматики ==
+говорят что КС-грамматика находится в нормальной форме Хомского если каждое правило имеет вид:
+# Либо A &rarr; BC, A,B,C - нетерминалы
+# либо A &rarr; &alpha;, &alpha; - терминал
+# либо S &rarr; e, в таком случае S не встречается в правых частях правил
+== Определение правостороннего вывода в КС-грамматике ==
+Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого нетерминала, называется '''правосторонним'''.
+== Определение левостороннего вывода в КС-грамматике ==
+Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется '''левосторонним'''.
+== Что такое леворекурсивная грамматика? ==
+'''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A &rArr;<sup>+</sup> Au для некоторой строки u.
+== Определение множества FIRST1 ==
+FIRST1 — множество всех терминальных символов, с которых может начинаться цепочка терминальных символов, выводимых из цели грамматики или ε, если u ⇒* ε.
+Пример:
+    * S → aS | A
+    * A → b | bSd | bA | ε
+    * FIRST1 = {a, b, ε}
+== Определение множества FOLLOW1 ==
+== Определение LL(1) грамматики ==
+LL(1)-грамматика - грамматика, для которой таблица предсказывающего анализатора не имеет неоднозначно определенных входов
+== Определение LR(1) ситуации ==
+LR(1)-ситуацией называется пара [''A''&nbsp;&rarr;&nbsp;&alpha; . &beta;, ''a''], где ''A''&nbsp;&rarr;&nbsp;&alpha; &beta;&nbsp;— правило грамматики, ''a''&nbsp;— терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.
+== Определение LR(1) грамматики ==
+Грамматика называется LR(1), если из условий
+. <math>S' =>_r uAw =>_r uvw</math>,
+. <math>S' =>_r zBx =>_r uvy</math>,
+. FIRST(w) = FIRST(y)
+следует, что uAy = zBx (т.е. u = z, A = B и x = y).
+== Какого типа конфликты могут появиться в канонической системе множеств LR(1) ситуаций? ==
+Shift-Reduce и Reduce-Reduce
+== Определение конфигурации LR-анализатора ==
+Пара (Содержимое магазина, непросмотренный вход)
+== Как меняется конфигурация LR-анализатора при действии reduce? ==
+Убрать из стека правую часть правила, добавить левую и состояние goto(последнее состояние в магазине, символ из левой части правила)
+== Какие типы действий выполняет LR-анализатор? ==
+Shift, Reduce, Accept, Reject
+== Как меняется конфигурация LR-анализатора при действии shift? ==
+Перенести верхний символ входа в магазин, занести наверх магазина состояние action(предыдущее состояние, взятый символ)
+== Что такое основа правой сентенциальной формы ==
+Основа правой сентенциальной формы z - это правило вывода <math>A -> v</math> и позиция в z, в которой может быть найдена цепочка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если <math>S =>_r avb</math>, то <math>A -> v</math> в позиции, следующей за a - это основа цепочки <math>avb</math>. Подцепочка b справа от основы содержит только терминальные символы.
 {{Курс Конструирование Компиляторов}}