Редактирование: Конструирование Компиляторов, Определения
Материал из 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 |
== Неоднозначная грамматика == | == Неоднозначная грамматика == | ||
Строка 79: | Строка 79: | ||
== Расширенный магазинный автомат == | == Расширенный магазинный автомат == | ||
- | |||
- | Отличается от магазинного автомата только областью определения D. | ||
- | |||
'''Расширенный магазинный автомат''' — M = (Q, T, Г, D, q<sub>0</sub>, z<sub>0</sub>, F) | '''Расширенный магазинный автомат''' — M = (Q, T, Г, D, q<sub>0</sub>, z<sub>0</sub>, F) | ||
* Q — конечное множество состояний | * Q — конечное множество состояний | ||
Строка 92: | Строка 89: | ||
== Грамматика в нормальной форме Хомского == | == Грамматика в нормальной форме Хомского == | ||
- | + | '''Грамматика''' находится '''в нормальной форме Хомского''', если правила вывода имеют вид: | |
- | Грамматика находится '''в нормальной форме Хомского''', если правила вывода имеют вид: | + | * 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 ≠ ε | ||
Строка 112: | Строка 108: | ||
x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку | x — '''непорождающий символ''', если из него нельзя вывести терминальную цепочку | ||
- | x — '''непорождающий символ''', если не существует вывода x ⇒* w, w ∈ T* | + | x — '''непорождающий символ''', если из не существует вывода x ⇒* w, w ∈ T* |
== Бесполезный символ == | == Бесполезный символ == |