Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 41 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

41
{ a
n
b
n
c
n
| n ≥ 0 }
является контекстно-зависимым, а не контекстно-свободным.
Контекстно-свободные грамматики имеют ряд характеристик, для
которых справедливы следующие положения.
1) Каноническая форма
а) Каждая КС-грамматика эквивалентна (т.е. генерирует тот же язык)
грамматике в нормальной форме Хомского
, т.е. со всеми порождающими
правилами вида
A
→
BC | a
при обычных условиях, касающихся терминалов и нетерминалов.
б) Каждая КС-грамматика эквивалентна грамматике в нормальной
форме Грейбаха, т.е. со всеми порождающими правилами вида
A
→
bα
где α – строка нетерминалов (возможно, пустая).
2) Самовложение
Если в грамматике G есть нетерминал A, для которого
A
⇒
α
1
A α
2
(здесь α
1
и α
2
являются непустыми строками терминалов и/или
нетерминалов), то о такой грамматике говорят, что она содержит
самовложение. Например, две приведенные ниже грамматики содержат
самовложение:
1) G
1
= ({S}, {a, b}, P, S), где элементы P:
S
→
aSb
S
→
ε
2) G
2
= ({S, A}, {begin, end,[,]}, P, S), где элементы P:
S
→
begin A end
S
→
ε
A
→
[S]
В последнем случае об A и S говорят, что они проявляют свойство
самовложения. Теоретически любая КС-грамматика, не содержащая 
                                                                              41
         n    n   n
     {a b c |n≥0}
     является контекстно-зависимым, а не контекстно-свободным.
     Контекстно-свободные грамматики имеют ряд характеристик, для
которых справедливы следующие положения.
1) Каноническая форма
     а) Каждая КС-грамматика эквивалентна (т.е. генерирует тот же язык)
грамматике в нормальной форме Хомского, т.е. со всеми порождающими
правилами вида
     A → BC | a
     при обычных условиях, касающихся терминалов и нетерминалов.
     б) Каждая КС-грамматика эквивалентна грамматике в нормальной
форме Грейбаха, т.е. со всеми порождающими правилами вида
     A → bα
где α – строка нетерминалов (возможно, пустая).
2) Самовложение
     Если в грамматике G есть нетерминал A, для которого
     A ⇒ α1 A α2
(здесь   α1       и   α2   являются   непустыми   строками   терминалов    и/или
нетерминалов), то о такой грамматике говорят, что она содержит
самовложение. Например, две приведенные ниже грамматики содержат
самовложение:
     1) G1 = ({S}, {a, b}, P, S), где элементы P:
     S → aSb
     S→ε
     2) G2 = ({S, A}, {begin, end,[,]}, P, S), где элементы P:
     S → begin A end
     S→ε
     A → [S]
     В последнем случае об A и S говорят, что они проявляют свойство
самовложения.         Теоретически    любая   КС-грамматика,     не   содержащая

Страницы