ВУЗ:
Составители:
множества *}{
TA
VV U ,
A
VA ∈ и
λ
η
≠
;
1
ξ
и
2
ξ
называют соответственно левым
и правым контекстом. Поэтому НС-грамматики называют еще контекстно
зависимыми грамматиками. Класс языков, порождаемых НС-грамматиками,
совпадает с классом языков, порождаемых неукорачивающими
грамматиками.
2-й класс составляют контекстно-свободные (КС) грамматики, или
бесконтекстные грамматики, которые являются сужением класса НС-
грамматик. КС-грамматики - это неукорачивающие грамматики с правилами
вывода
типа
η
→А , в которых
A
VА
∈
, *}{
TA
VV U
∈
η
, причем
λ
η
≠ . КС-
грамматики порождают КС-языки, являющиеся хорошей моделью языков
программирования.
3-й класс составляют укорачивающие КС-грамматики (УКС-
грамматики). Правила вывода УКС-грамматик имеют тот же вид, что и в КС-
грамматиках, но цепочка
η
может быть пустой.
4-й класс образуют автоматные грамматики (А-грамматики). Правила
вывода в них наиболее просты и имеют вид
вВА → и вА → , где
А
VВА
∈
, ,
Т
VВ ∈ . Такие А-грамматики называются правосторонними. Если грамматики
содержат правила
ВвА → , то они называются левосторонними. В них могут
включаться также правила вывода
λ
→А
. А-грамматики порождают А-языки
и интересны тем, что с их помощью можно описать преобразователи
информации, называемые конечными автоматами.
Приведенная классификация, естественно, не охватывает все типы
порождающих грамматик. Существуют промежуточные классы, например,
между НС- и Кс-грамматиками, между КС- и А-грамматиками. Однако,
специально на этом мы останавливаться не будем
.
Страницы
- « первая
- ‹ предыдущая
- …
- 48
- 49
- 50
- 51
- 52
- …
- следующая ›
- последняя »
