ВУЗ:
Составители:
Рубрика:
20
Определение. Цепочка w допускается МП–автоматом M = (K, Σ,
Γ
,
δ
, Z
0
,
q
0
, F), если (полагаем (q
0
, w, Z
0
) (q,
ε, α
) для некоторых q ∈ F,
α
∈
Γ
*. Мно-
жество всех цепочек, допускаемых МП–автоматом M, обозначается T(M). Заме-
тим, что
ε
∈ F.
Формальные грамматики дают естественный способ упорядочения язы-
ков с помощью ограничений, которые можно ввести в продукции (правила пе-
реписывания). Перечислим их в порядке убывания мощности:
Язык типа 0, или язык без ограничений, порождается грамматикой, в ко-
торой все продукции имеют вид x → y, где x и y — цепочки
в V* (словаре грам-
матики).
Язык типа 1, или контекстно-зависимый язык, порождается граммати-
кой, в которой все продукции имеют вид x → y и, кроме того, число | y | симво-
лов в y не меньше числа символов в x. Значимость этого ограничения лучше
всего оценить, анализируя продукцию, нарушающую его. Например, правило
(S
1
+ S
2
) – S
2
→ S
1
. Можно показать, что язык, порождаемый контекстно-
зависимой грамматикой, может порождаться также грамматикой, в которой все
продукции имеют вид xAy → xwy, где w, x и y — цепочки в V*, а A — перемен-
ная (нетерминал). Продукцию xAy → xwy можно интерпретировать так:
Цепочка w выводима из A, если А появляется в контексте x и y.
Таким образом, правило переписывания xAy → xwy дает интуитивно бо-
лее понятное определение контекстно-зависимой грамматики.
Язык типа 2, или контекстно-свободный язык, порождается граммати-
кой, в которой все продукции имеют вид A → x, где, как и раньше, A — нетер-
минал, а x — цепочка в V*.
Язык типа 3, или
регулярный язык, порождается грамматикой, продукции
которой имеют вид A → aB или A → a, где a — терминал, а B— нетерминал.
Определение. Цепочка w допускается МП–автоматом M = (K, Σ, Γ, δ, Z0, q0, F), если (полагаем (q0, w, Z0) (q, ε, α) для некоторых q ∈ F, α ∈ Γ*. Мно- жество всех цепочек, допускаемых МП–автоматом M, обозначается T(M). Заме- тим, что ε ∈ F. Формальные грамматики дают естественный способ упорядочения язы- ков с помощью ограничений, которые можно ввести в продукции (правила пе- реписывания). Перечислим их в порядке убывания мощности: Язык типа 0, или язык без ограничений, порождается грамматикой, в ко- торой все продукции имеют вид x → y, где x и y — цепочки в V* (словаре грам- матики). Язык типа 1, или контекстно-зависимый язык, порождается граммати- кой, в которой все продукции имеют вид x → y и, кроме того, число | y | симво- лов в y не меньше числа символов в x. Значимость этого ограничения лучше всего оценить, анализируя продукцию, нарушающую его. Например, правило (S1 + S2) – S2 → S1 . Можно показать, что язык, порождаемый контекстно- зависимой грамматикой, может порождаться также грамматикой, в которой все продукции имеют вид xAy → xwy, где w, x и y — цепочки в V*, а A — перемен- ная (нетерминал). Продукцию xAy → xwy можно интерпретировать так: Цепочка w выводима из A, если А появляется в контексте x и y. Таким образом, правило переписывания xAy → xwy дает интуитивно бо- лее понятное определение контекстно-зависимой грамматики. Язык типа 2, или контекстно-свободный язык, порождается граммати- кой, в которой все продукции имеют вид A → x, где, как и раньше, A — нетер- минал, а x — цепочка в V*. Язык типа 3, или регулярный язык, порождается грамматикой, продукции которой имеют вид A → aB или A → a, где a — терминал, а B— нетерминал. 20
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »