Редактирование: Конструирование Компиляторов, Теоретический минимум (2012)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
- | ''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 | + | ''см. также [[Конструирование Компиляторов, Теоретический минимум|ответы на вопросы теоретического минимума 2007 года]], [[Конструирование Компиляторов, Определения|список определений]].'' |
== Алфавит == | == Алфавит == | ||
Строка 159: | Строка 159: | ||
== Определение эквивалентных состояний ДКА == | == Определение эквивалентных состояний ДКА == | ||
- | Два состояния <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 | + | Два состояния <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> |
== Определение различимых состояний ДКА == | == Определение различимых состояний ДКА == | ||
- | Два состояния <math>q_i</math> и <math>q_j</math> называются различимыми, если они не эквивалентны. | ||
== Определение контекстно-свободной грамматики без ε-правил == | == Определение контекстно-свободной грамматики без ε-правил == | ||
Строка 211: | Строка 210: | ||
# ''F'' ⊆ ''Q'' — множество заключительных состояний | # ''F'' ⊆ ''Q'' — множество заключительных состояний | ||
Кроме того, должны выполняться следующие условия: | Кроме того, должны выполняться следующие условия: | ||
- | # Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q'' ∈ ''Q'', ''a'' ∈ ''T'' ∪ {ε}, ''Z'' ∈ ''Г'' | + | # Множество ''D''(''q'', ''a'', ''Z'') содержит не более одного элемента для любых ''q'' ∈ ''Q'', ''a'' ∈ ''T'' ∪ {ε}, ''Z''<sub>0</sub> ∈ ''Г'' |
# Если ''D''(''q'', ε, ''Z'') ≠ ∅, то ''D''(''q'', ''a'', ''Z'') = ∅ для всех ''a'' ∈ ''T'' | # Если ''D''(''q'', ε, ''Z'') ≠ ∅, то ''D''(''q'', ''a'', ''Z'') = ∅ для всех ''a'' ∈ ''T'' | ||
Строка 236: | Строка 235: | ||
== Определение нормальной формы Хомского для КС-грамматики == | == Определение нормальной формы Хомского для КС-грамматики == | ||
- | + | говорят что КС-грамматика находится в нормальной форме Хомского если каждое правило имеет вид: | |
- | + | # Либо A → BC, A,B,C - нетерминалы | |
- | # Либо A → BC | + | # либо A → α, α - терминал |
- | # | + | # либо S → e, в таком случае S не встречается в правых частях правил |
- | # | + | |
== Определение правостороннего вывода в КС-грамматике == | == Определение правостороннего вывода в КС-грамматике == |