Изменения

Перейти к: навигация, поиск

Иерархия Хомского формальных грамматик

1 байт добавлено, 00:49, 5 ноября 2011
м
Класс 1: пробел перед скобкой «(возможно правило»
{{Определение
|definition =
'''Контекстно-зависимые грамматики''' - это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha A \beta\rightarrow\alpha\gamma\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{*}</tex>, <tex>A \in N</tex> и <tex>\gamma \in \{\Sigma\cup N\}^{+}</tex>(возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).}}
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]] неукорачивающие грамматики эквивалентны контекстно зависимым.
editor
177
правок

Навигация