Языки и трансляции. Мартыненко Б.К. - 66 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

65
Если w
i
≠ε, то по индукционному предположению C
i
w
i
. Кроме того, из
правила A → C
1
C
2
... C
r
∈P, применённого на первом шаге рассматриваемого
вывода, по построению получается правило A →α
1
α
2
... α
r
∈P
1
, где α
i
= C
i
, если
w
i
≠ε, или α
i
= ε, если w
i
= ε. Следовательно, A w.
Из рассуждений I и II следует, что L(G
1
)=L(G).
Что и требовалось доказать.
Из теоремы 4.11 непосредственно следует тот факт, что единственная
разница между контекстно-свободной грамматикой с правилами вида A →ε и
грамматиками без ε-правил состоит в том, что первая может порождать пустое
предложение. Далее мы будем называть cfg с ε-правилами просто cfg, зная, что
эквивалентная грамматика без ε-правил (за исключением быть может S →ε)
может быть найдена.
§ 4.7. Специальные типы
контекстно-свободных языков
и грамматик
Здесь мы рассмотрим несколько ограниченных классов КС-языков.
Определение 4.6. Говорят, что контекстно-свободная грамматика G =(V
N
,
V
T
, P, S) — линейна, если каждое её правило имеет вид A → uBv или A → u, где
A, B∈V
N
, u,v ∈V
T
*
. Если v = ε, то грамматика называется праволинейной, если
u = ε, то она леволинейна.
Язык, который может порождаться линейной грамматикой, называется
линейным языком.
Не все контекстно-свободные языки являются линейными языками.
Заметим, что ни одна цепочка, выводимая в линейной грамматике, не имеет
более одного нетерминала.
Пример 4.4. Грамматика G =({S}, {0, 1}, P, S), где P ={S → 0S1, S →ε},
является линейной грамматикой, которая порождает язык L ={0
n
1
n
|n ≥ 0}.
Определение 4.7. Говорят, что грамматика G =(V
N
, V
T
, P, S) — последова-
тельная, если нетерминалы A
1
, A
2
,..., A
k
из словаря V
N
можно упорядочить так,
что если A
i
→α∈P, то α не содержит ни одного нетерминала A
j
с индексом j < i.
Язык, порождаемый последовательной грамматикой, называется
последовательным языком.
Пример 4.5. Грамматика G = ({A
1
, A
2
}, {0, 1}, P, A
1
), где P ={A
1
→ A
2
A
1
,
A
1
→ A
2
, A
2
→ 0A
2
1, A
2
→ε}, является последовательной грамматикой, которая
порождает язык L = {0
n
1
n
| n ≥ 0}
*
.
Определение 4.8. Если контекстно-свободный язык L над алфавитом V
T
есть подмножество языка w
1
*
w
2
*
... w
k
*
6
для некоторого k, где w
i
∈V
T
*
, i = 1, 2,..., k,
то говорят, что L
— ограниченный язык.
6
Строго говоря, w
1
*
w
2
*
... w
k
*
следовало бы записывать в виде {w
1
}
*
{w
2
}
*
... {w
k
}
*
. Но и без
скобок не возникает никаких недоразумений.
i
G
l
⇒
1
*
G
⇒

Страницы