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

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

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

Версия 17:49, 3 февраля 2008

Содержание

1 Определение грамматик типа 0 по Хомскому
2 Определение грамматик типа 1 (неукорачивающих) по Хомскому
3 Определение детерминированной машины Тьюринга
4 Определение недетерминированной машины Тьюринга
5 Определение конфигурации машины Тьюринга
6 Определение языка, допускаемого машиной Тьюринга
7 Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга
8 Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга
9 Определение линейно-ограниченного автомата
10 Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми линейно-ограниченными автоматами
11 Определение регулярного множества
12 Определение регулярного выражения
13 Определение праволинейной грамматики
14 Определение недетерминированного конечного автомата
15 Определение детерминированного конечного автомата
16 Объяснить разницу между недетерминированным и детерминированным конечным автоматом
17 Определение конфигурации конечного автомата
18 Определение языка, допускаемого конечным автоматом
19 Определение ε-замыкания для подмножества состояний НКА
20 Определение расширенной функции переходов для КА
21 Определение функции firstpos для поддерева в дереве регулярного выражения
22 Определение функции lastpos для поддерева в дереве регулярного выражения
23 Определение функции followpos для позиций в дереве регулярного выражения
24 Сформулировать соотношение между регулярными множествами и языками, допускаемыми КА
25 Определение регулярной грамматики
26 Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами
27 Определение контекстно-свободной грамматики
28 Определение левостороннего вывода в КС-грамматике
29 Определение правостороннего вывода в КС-грамматике
30 Определение сентенциальной формы
31 Определение приведенной грамматики
32 Определение множества FOLLOW(A)
33 Определение LR(1) ситуации
34 Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА
35 Определение однозначной КС-грамматики
36 Определение неоднозначной КС-грамматики
37 Определение контекстно-свободной грамматики без ε-правил
38 Определение вывода в КС-грамматике
39 Определение языка, порождаемого КС-грамматикой
40 Определение недетерминированного МП автомата
41 Определение детерминированного МП автомата
42 Определение конфигурации МП автомата
43 Определение языка, допускаемого МП автоматом
44 Определение недетерминированного МП автомата, допускающего опустошением магазина
45 Определение множества FIRST(u)
46 Определение замыкания множества LR(1) ситуаций
47 Что такое леворекурсивная грамматика?

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

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

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

Если

Каждое правило грамматики, кроме S → ε, имеет вид α → β, |α| ≤ |β|
В том случае, когда S → ε ∈ P, символ S не встречается в правых частях правил

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

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

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

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

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

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

Q — конечное множество состояний
Г — конечное множество символов (конечный алфавит)
Σ — входной алфавит
D — правила перехода
- D: (Q\F) × Г → 2^{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.

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

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

Определение линейно-ограниченного автомата

Линейно-ограниченный автомат — это недетерминированная машина Тьюринга, которая не может выходить за область входной строки.

Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми линейно-ограниченными автоматами

Линейно-ограниченные автоматы распознают контекстно-зависимые языки (то есть языки класса 1). Языки класса 0 распознаются только машинами Тьюринга с неограниченной памятью.

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

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

{} (пустое множество) — регулярное множество в алфавите T
{a} — регулярное множество в алфавите T для каждого a ∈ T
{ε} — регулярное множество в алфавите T
Если P и Q — регулярные множества в алфавите T, то таковы же и множества
- P ∪ Q (объединение)
- PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q)
- P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …)
Ничто другое не является регулярным множеством в алфавите 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*).

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

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

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

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

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

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

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

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

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

Сентенциальная форма — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы

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

Грамматика называется приведённой, если она не содержит бесполезных символов.

Определение множества FOLLOW(A)

Пусть A — нетерминал. Тогда FOLLOW(A) — множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме, то есть, множество терминалов a таких, что существует вывод вида S ⇒* uAav для некоторых u и v.

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

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

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

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

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

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

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

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

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

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

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

Определим на множестве (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}

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

Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка 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. В таком случае говорят, что автомат допускает цепочку опустошением магазина.

Определение множества FIRST(u)

Если u — любая строка символов грамматики, положим FIRST(u) — множество терминалов, с которых начинаются строки, выводимые из u. Если u ⇒* ε, то ε так же принадлежит FIRST(u).

Определение замыкания множества LR(1) ситуаций

Пусть есть множество ситуаций I тогда определим функцию closure(I) как добавление к I ситуаций вида [B → .γ, b] для каждых ситуации [A → α.Bβ, a], правила вывода B → γ, принадлежащего Г, каждого терминала b из FIRST(βa), пока это возможно.

//Ильдар: Мне кажется это не совсем определение, а процедура построения. Я бы предварительно написал, что замыкание множества LR(1)-ситуаций, допустимых для некоторого активного префикса z, - это множество всех LR(1)-ситуаций, допустимых для этого префикса.

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

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

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

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.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_%282007%29

@@ Строка 1: / Строка 1: @@
-== From Ebaums Inc to MurkLoar. ==
+== Определение грамматик типа 0 по Хомскому ==
-We at EbaumsWorld consider you as disgrace of human race.
+Если на грамматику G = (N, T, P, S) не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений.
-Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-Dig yourself a grave - you will need it.
+== Определение грамматик типа 1 (неукорачивающих) по Хомскому ==
+Если
+# Каждое правило грамматики, кроме S &rarr; &epsilon;, имеет вид &alpha; &rarr; &beta;, |&alpha;| &le; |&beta;|
+# В том случае, когда S &rarr; &epsilon; &isin; P, символ S не встречается в правых частях правил
+то грамматику называют грамматикой типа 1, или неукорачивающей.
+== Определение детерминированной машины Тьюринга ==
+'''Детерминированная машина Тьюринга''' — T<sub>m</sub> = (Q, Г, &Sigma;, D, q<sub>0</sub>, F)
+* Q — конечное множество состояний
+* Г — конечное множество символов (конечный алфавит)
+* &Sigma; — входной алфавит
+* D — правила перехода
+** D: (Q\F) &times; Г &rarr; Q &times; Г &times; {L, R}
+* q<sub>0</sub> &isin; Q — начальное состояние
+* F &sube; Q — множество конечных состояний
+== Определение недетерминированной машины Тьюринга ==
+'''Недетерминированная машина Тьюринга''' — T<sub>m</sub> = (Q, Г, &Sigma;, D, q<sub>0</sub>, F)
+* Q — конечное множество состояний
+* Г — конечное множество символов (конечный алфавит)
+* &Sigma; — входной алфавит
+* D — правила перехода
+** D: (Q\F) &times; Г &rarr; 2<sup>Q &times; Г &times; {L, R}</sup>
+* 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 — положение головки машины Тьюринга
+== Определение языка, допускаемого машиной Тьюринга ==
+Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q<sub>0</sub>, w, 1) может достигнуть через конечное число переходов состояния q &isin; F.
+== Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга ==
+Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0.
+== Объяснить разницу между недетерминированной и  детерминированной машиной Тьюринга ==
+Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает.
+== Определение линейно-ограниченного автомата ==
+'''Линейно-ограниченный автомат''' — это недетерминированная машина Тьюринга, которая не может выходить за область входной строки.
+== Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми линейно-ограниченными автоматами ==
+Линейно-ограниченные автоматы распознают контекстно-зависимые языки (то есть языки класса 1). Языки класса 0 распознаются только машинами Тьюринга с неограниченной памятью.
+<!--
+Часто в определении линейно-ограниченного автомата длину ленты считают равной L = a + b*l, где l - длина входа. ЛОА с таким ограничением принимают тот же класс языков, что и ЛОА с L = l.
+-->
+<!--
+Так как для любой заданной грамматики типа 0 можно построить машину Тьюринга, которая будет проверять слова, порождаемые данной грамматикой, и при этом в процессе работы будет использовать некое заранее заданное пространство (то есть, данная машина Тьюринга будет являться линейно-ограниченным автоматом), то рассматриваемые языки эквивалентны.
+ это исключительно на моей совести. Нигде этого я не нашёл, пришлось выводить из эквивалентности языков грамматик уровня 0 и МТ — ~~~~
+Тут используется ограниченность при некотором конкретном вводе, но требуется ограниченность (тем более линейная) для просизвольного ввода длины l. Доказательство неверно, как и доказываемый факт.
+-->
+== Определение регулярного множества ==
+'''Регулярное множество''' в алфавите T определяется следующим образом:
+* {} (пустое множество) — регулярное множество в алфавите T
+* {a} — регулярное множество в алфавите T для каждого a &isin; T
+* {&epsilon;} — регулярное множество в алфавите T
+* Если P и Q — регулярные множества в алфавите T, то таковы же и множества
+** P &cup; Q (объединение)
+** PQ (конкатенация, то есть множество таких pq, что p &isin; P, q &isin; Q)
+** P* (итерация: P* = {&epsilon;} &cup; P &cup; PP &cup; PPP &cup; &hellip;)
+* Ничто другое не является регулярным множеством в алфавите 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*).
+== Соотношение, между языками, порождаемыми КС-грамматиками, и языками, допускаемыми недетерминированными МП автоматами ==
+Они совпадают.
+== Определение контекстно-свободной грамматики ==
+A &rarr; &alpha;, &alpha; &isin; (N &cup; T)*
+== Определение левостороннего вывода в КС-грамматике ==
+Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется '''левосторонним'''.
+== Определение правостороннего вывода в КС-грамматике ==
+Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого правого нетерминала, называется '''правосторонним'''.
+== Определение сентенциальной формы ==
+'''Сентенциальная форма''' — последовательность символов (терминалов и нетерминалов), выводимых из аксиомы
+== Определение приведенной грамматики ==
+'''Грамматика''' называется '''приведённой''', если она не содержит бесполезных символов.
+== Определение множества FOLLOW(A) ==
+Пусть A — нетерминал. Тогда '''FOLLOW(A)''' — множество терминалов a, которые могут появиться непосредственно справа от A в некоторой [[#Сентенциальная форма|сентенциальной форме]], то есть, множество терминалов a таких, что существует вывод вида S &rArr;* uAav для некоторых u и v.
+== Определение LR(1) ситуации ==
+LR(1)-ситуацией называется пара [''A''&nbsp;&rarr;&nbsp;&alpha; &beta;, ''a''], где ''A''&nbsp;&rarr;&nbsp;&alpha; &beta;&nbsp;— правило грамматики, ''a''&nbsp;— терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.
+== Сформулировать соотношение между языками, порождаемыми праволинейными грамматиками и языками, допускаемыми КА ==
+Для любой праволинейной грамматики существует конечный автомат, проверяющий порождаемый грамматикой язык. Для любого конечного автомата существует праволинейная грамматика, порождающая проверяемый конечным автоматом язык.
+== Определение однозначной КС-грамматики ==
+КС грамматика называется однозначной или детерминированной, если всякая выводимая терминальная цепочка имеет только одно дерево вывода (соотвественно только один левый и только один правый вывод).
+== Определение неоднозначной КС-грамматики ==
+КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка α ⊂ L(G), для которой может быть построено два или более различных деревьев вывода.
+== Определение контекстно-свободной грамматики без &epsilon;-правил ==
+* A &rarr; &alpha;, &alpha; &isin; (N &cup; T)<sup>+</sup>
+* допускается S &rarr; &epsilon;, если S не входит ни в какую правую часть
+== Определение вывода в КС-грамматике ==
+Определим на множестве (''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''}
+== Определение недетерминированного МП автомата ==
+Недетерминированный автомат с магазинной памятью (МП-автомат) — семёрка ''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''. В таком случае говорят, что автомат допускает цепочку ''опустошением магазина''.
+== Определение множества FIRST(u) ==
+Если u — любая строка символов грамматики, положим FIRST(u) — множество терминалов, с которых начинаются строки, выводимые из u. Если u &rArr;* &epsilon;, то &epsilon; так же принадлежит FIRST(u).
+== Определение замыкания множества LR(1) ситуаций ==
+Пусть есть множество ситуаций ''I'' тогда определим функцию ''closure''(''I'') как добавление к ''I'' ситуаций вида [''B''&nbsp;&rarr;&nbsp;.''&gamma;'', ''b''] для каждых ситуации [''A''&nbsp;&rarr;&nbsp;''&alpha;.B&beta;'', ''a''], правила вывода ''B''&nbsp;&rarr;&nbsp;''&gamma;'', принадлежащего ''Г'', каждого терминала ''b'' из ''FIRST''(''&beta;a''), пока это возможно.
+//Ильдар:
+Мне кажется это не совсем определение, а процедура построения. Я бы предварительно написал, что замыкание множества LR(1)-ситуаций, допустимых для некоторого активного префикса z, - это множество всех LR(1)-ситуаций, допустимых для этого префикса.
+== Что такое леворекурсивная грамматика? ==
+'''Грамматика''' называется '''леворекурсивной''', если в ней имеется нетерминал A такой, что существует вывод A &rArr; Au для некоторой строки u.
+{{Курс Конструирование Компиляторов}}