Редактирование: Конструирование Компиляторов, Определения
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 60: | Строка 60: | ||
== Лемма о разрастании == | == Лемма о разрастании == | ||
- | Если язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 < |y | + | Если язык L — регулярный, то ∃ k: ∀ w ∈ L, |w| ≥ k | w = xyz, 0 < |y| ≤ k, xy<sup>i</sup>z ∈ L, ∀ i ≥ 0 |
== Неоднозначная грамматика == | == Неоднозначная грамматика == | ||
Строка 92: | Строка 92: | ||
== Грамматика в нормальной форме Хомского == | == Грамматика в нормальной форме Хомского == | ||
- | + | '''Грамматика''' находится '''в нормальной форме Хомского''', если правила вывода имеют вид: | |
- | Грамматика находится '''в нормальной форме Хомского''', если правила вывода имеют вид: | + | * A → BC; B, C ∈ N |
- | + | * A → a | |
- | + | * S → ε (если ε ∈ L; S не входит ни в одну правую часть) | |
- | + | ||
== Лемма о разрастании (для контекстно-свободного языка) == | == Лемма о разрастании (для контекстно-свободного языка) == | ||
- | Для любого контекстно-свободного языка L ∃ l, k: | + | Для любого контекстно-свободного языка L ∃ l, k: α ∈ L, |α| > l, α = uvwxy |
# |vwx| ≤ k | # |vwx| ≤ k | ||
# vx ≠ ε | # vx ≠ ε |