Редактирование: Конструирование Компиляторов, Определения
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 26: | Строка 26: | ||
== Иерархия по Хомскому == | == Иерархия по Хомскому == | ||
- | * | + | * 0: произвольные грамматики |
- | * | + | * 1: неукорачивающие (контекстно-зависимые) грамматики |
** α → β, |α| ≤ |β| | ** α → β, |α| ≤ |β| | ||
** допускается S → ε, если S не входит ни в какую правую часть | ** допускается S → ε, если S не входит ни в какую правую часть | ||
- | * | + | * 2: контекстно-свободные |
** A → α, α ∈ (N ∪ T)* | ** A → α, α ∈ (N ∪ T)* | ||
- | * | + | * 3: праволинейные (A → w, A → wB, w ∈ T*), леволинейные (A → w, A → Bw, w ∈ T*), |
Из определения следует, что Z<sub>0</sub> ⊇ Z<sub>1</sub> ⊇ Z<sub>2</sub> ⊇ Z<sub>3</sub>. | Из определения следует, что Z<sub>0</sub> ⊇ Z<sub>1</sub> ⊇ Z<sub>2</sub> ⊇ Z<sub>3</sub>. | ||
- | Существует теорема, которая доказывает | + | Существует теорема, которая доказывает, что Z<sub>0</sub> ⊃ Z<sub>1</sub> ⊃ Z<sub>2</sub> ⊃ Z<sub>3</sub>. |
== Машина Тьюринга == | == Машина Тьюринга == |