Редактирование: Конструирование Компиляторов, Теоретический минимум (2009)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 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 по Хомскому == | ||
Строка 27: | Строка 23: | ||
Грамматика типа 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> | Грамматика типа 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, Г, Σ, D, q<sub>0</sub>, F) | ||
- | * Q — конечное множество состояний | ||
- | * Г — конечное множество ленточных символов (конечный алфавит), один из которых называется пустым и обозначается обычно b | ||
- | * Σ — входной алфавит, Σ ⊆ Г\{b} (b - пустой символ) | ||
- | * D — правила перехода | ||
- | ** D: (Q\F) × Г → Q × Г × {L, R} | ||
- | * q<sub>0</sub> ∈ Q — начальное состояние | ||
- | * F ⊆ Q — множество конечных состояний | ||
- | |||
- | |||
- | |||
- | == Определение конфигурации машины Тьюринга == | ||
- | Конфигурацией машины Тьюринга называется тройка (q, w, i), где | ||
- | * q ∈ Q — состояние машины Тьюринга | ||
- | * w ∈ Г* —текущее содержимое занятого участка ленты, w = a<sub>1</sub> … a<sub>n</sub> | ||
- | * i ∈ Z — положение головки машины Тьюринга | ||
- | |||
- | == Определение языка, допускаемого машиной Тьюринга == | ||
- | Язык, допускаемый машиной Тьюринга — множество таких слов w, что, машина Тьюринга, находясь в состоянии (q<sub>0</sub>, w, 1) может достигнуть через конечное число переходов состояния q ∈ F. | ||
- | |||
- | == Соотношение между языками, порождаемыми грамматиками типа 0 и языками, допускаемыми машинами Тьюринга == | ||
- | Класс языков, допускаемых машиной Тьюринга, эквивалентен классу языков, порождаемых грамматиками типа 0. | ||
- | |||
- | == Объяснить разницу между недетерминированной и детерминированной машиной Тьюринга == | ||
- | Детерминированная машина Тьюринга из данного состояния по данному символу может сделать не более одного перехода, недетерминированная же таким свойством не обладает. | ||
== Определение регулярного множества == | == Определение регулярного множества == |