Редактирование: Конструирование Компиляторов, Теоретический минимум (2009)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 30 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].'' | ''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].'' | ||
| - | == Алфавит == | ||
| - | |||
| - | Алфавит - конечное множество символов | ||
| - | |||
== Определение грамматики == | == Определение грамматики == | ||
| - | Грамматика | + | Грамматика G = (N,T,P,S) - четверка множеств, где |
| - | * | + | * N - алфавит нетерминальных символов |
| - | * | + | * T - алфавит терминальных символов, <math>N \cap T = \empty</math>; |
| - | * | + | * P - множество правил вида α → β, α ∈ ( N ∪ T)*N(N ∪ T)*, β ∈ (N ∪ T)* |
| - | * | + | * S ∈ N - начальный символ или аксиома грамматики |
== Определение грамматик типа 0 по Хомскому == | == Определение грамматик типа 0 по Хомскому == | ||
| - | Если на грамматику | + | Если на грамматику G = (N, T, P, S) не накладываются никакие ограничения, то её называют грамматикой типа 0, или грамматикой без ограничений. |
== Определение грамматик типа 1 (неукорачивающих) по Хомскому == | == Определение грамматик типа 1 (неукорачивающих) по Хомскому == | ||
Если | Если | ||
| - | # Каждое правило грамматики, кроме | + | # Каждое правило грамматики, кроме S → ε, имеет вид α → β, |α| ≤ |β| |
| - | # В том случае, когда | + | # В том случае, когда S → ε ∈ P, символ S не встречается в правых частях правил |
то грамматику называют грамматикой типа 1, или неукорачивающей. | то грамматику называют грамматикой типа 1, или неукорачивающей. | ||
| - | |||
| - | == Грамматика типа 2 (Контекстно-свободная, КС) по Хомскому == | ||
| - | |||
| - | Грамматика типа 2 (Контекстно-свободная, КС) - грамматика, где каждое правило <math>p \in P</math> имеет вид <math>A \rarr \alpha</math>, где <math> A \in N, \alpha \in (N \cup T)^*</math> | ||
| - | |||
| - | == Грамматика типа 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> | ||
== Определение детерминированной машины Тьюринга == | == Определение детерминированной машины Тьюринга == | ||
| Строка 38: | Строка 26: | ||
* F ⊆ Q — множество конечных состояний | * F ⊆ Q — множество конечных состояний | ||
| - | + | == Определение недетерминированной машины Тьюринга == | |
| + | '''Недетерминированная машина Тьюринга''' — T<sub>m</sub> = (Q, Г, Σ, D, q<sub>0</sub>, F) | ||
| + | * Q — конечное множество состояний | ||
| + | * Г — конечное множество символов (конечный алфавит) | ||
| + | * Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ) | ||
| + | * D — правила перехода | ||
| + | ** D: (Q\F) × Г → 2<sup>Q × Г × {L, R}</sup> | ||
| + | * q<sub>0</sub> ∈ Q — начальное состояние | ||
| + | * F ⊆ Q — множество конечных состояний | ||
== Определение конфигурации машины Тьюринга == | == Определение конфигурации машины Тьюринга == | ||
| Строка 58: | Строка 54: | ||
'''Регулярное множество''' в алфавите T определяется следующим образом: | '''Регулярное множество''' в алфавите T определяется следующим образом: | ||
| - | * | + | * {} (пустое множество) — регулярное множество в алфавите T |
| - | * | + | * {a} — регулярное множество в алфавите T для каждого a ∈ T |
| - | * | + | * {ε} — регулярное множество в алфавите T |
| - | * Если P и Q — регулярные множества в алфавите T, то | + | * Если P и Q — регулярные множества в алфавите T, то таковы же и множества |
| - | ** | + | ** P ∪ Q (объединение) |
| - | ** | + | ** PQ (конкатенация, то есть множество таких pq, что p ∈ P, q ∈ Q) |
| - | ** | + | ** P* (итерация: P* = {ε} ∪ P ∪ PP ∪ PPP ∪ …) |
* Ничто другое не является регулярным множеством в алфавите T | * Ничто другое не является регулярным множеством в алфавите T | ||
