Составители:
18
Определение 2.8. Грамматика G = (V
N
, V
T
, P, S) является грамматикой типа 2
или
контекстно-свободной грамматикой, если каждое её правило имеет вид
A → β∈ P, где A∈V
N
, β∈V
+
.
Вместо термина “контекстно-свободная грамматика” часто используют
аббревиатуру cfg (
context-free grammar) или сокращение КС-грамматика.
Замечание 2.2. Правило вида A →β позволяет заменить A на β независимо от
контекста, в котором появляется A.
Грамматика, приведенная в примере 2.1, является контекстно-свободной.
Пример 2.3. Рассмотрим интересную контекстно-свободную грамматику
G =(V
N
, V
T
, P, S), где V
N
={S, A, B}, V
T
={a, b},
P = {S → aB, S → bA, A → a, A → aS, A → bAA, B → b, B → bS, B → aBB}.
Покажем, что
L(G) = {x∈ {a, b}
+
| #
a
x =#
b
x}, где #
a
x обозначает число букв
а в цепочке x, а #
b
x число букв b в той же цепочке.
Другими словами, язык, порождаемый этой грамматикой, состоит из
непустых цепочек, в которых число букв
а и b одинаково.
Докажем для
+
T
,
x
V∈
что
1)
S x тогда и только тогда, когда x состоит из равного числа букв a и b;
2)
A x тогда и только тогда, когда x имеет на одно a больше, чем b;
3)
B x тогда и только тогда, когда x имеет на одно b больше, чем a.
I. Необходимость (индукция по длине вывода
l ≥ 1).
База (l = 1) . Очевидно, утверждение 1) доказывать нет необходимости, т. к.
выводов такого вида длины 1 не существует.
Два других утверждения выполняются, поскольку выводы вида 2) и 3)
длины 1 существуют:
A a, B b, и число букв их результатов удовлетворяют
условиям #
a
a =#
b
a + 1 и #
a
b =#
b
b − 1 соответственно.
Индукционная гипотеза. Предположим, что утверждения 1) – 3), выполня-
ются для всех
x, длина выводов которых меньше k (k ≥ 1).
Индукционный переход. Покажем, что они истинны для l = k + 1.
Если
S
x, то вывод должен начинаться либо с правила S → aB, либо с
правила
S → bA. В первом случае имеем S aB ax
1
= x, B
x
1
, так что по
индукционной гипотезе #
b
x
1
−#
a
x
1
=1 и, следовательно, #
a
x =#
b
x.
Аналогичное рассуждение достигает цели, если вывод начинается с
правила
S → bA.
Если A
x, то этот вывод может начаться либо с правила A → aS, либо с
правила A → bAA. В первом случае имеем A aS ax
1
= x, S
x
1
, так что по
индукционной гипотезе #
a
x
1
=#
b
x
1
и, следовательно, #
a
x −#
b
x = 1.
Во втором случае имеем
A
bAA
bx
1
A bx
1
x
2
, A x
1
, A x
2
, k
1
+ k
2
= k,
так что по индукционной гипотезе, поскольку
k
1
< k и k
2
< k, выполняются
соотношения #
a
x
1
− #
b
x
1
= 1, #
a
x
2
− #
b
x
2
=1 и, следовательно, #
a
x −#
b
x = 1.
Утверждение 3) доказывается аналогично 2).
*
⇒
*
⇒
*
⇒
⇒
1
k−
⇒
k
⇒
⇒⇒
k
⇒
⇒
1
k
⇒
⇒
2
k
⇒
2
k
⇒
1
k
⇒
1
k+
⇒
k
⇒
k
⇒
Страницы
- « первая
- ‹ предыдущая
- …
- 17
- 18
- 19
- 20
- 21
- …
- следующая ›
- последняя »
