Page 20 - 4625

2
1
w  w , … w n−1  w . Або кажуть, що бінарне відображен-
1
∗
ня  - це рефлексивно-транзитивне замикання бінарного
відношення  .
3. Мова, яку породжує граматика G (позначається L(G))
– це множина термінальних ланцюжків:
∗
L(G) = {w | S  w, w ∈ Σ }.
∗
Твердження: Клас мов, що породжуються праволінійни-
ми граматиками, співпадає з класом мов, які розпізнаються
скінченними автоматами.
Доведення. Спочатку покажемо, що для довільної право-
лінійної граматики G можна побудувати скінченний автомат
М, такий що L(M) = L(G).
Розглянемо правила праволінійної граматики. Вони бува-
ють двох типів:
∗
A wA , A , A  N, w ∈ Σ ;
i
i
j
j
∗
A w, w ∈ Σ .
i
На основі правил граматики G побудуємо схему P
1
нової граматики, яка буде еквівалентною початковій, а саме:
- правила виду A  a a …a A замінимо послідовніс-
i
p j
1 2
тю правил:
A  a B
i
1
1
B  a B
1
2 2
…………….
B p−1 a A ;
p
j
- правила виду A  a a …a замінимо послідовністю
i
p
1 2
правил:
A  a B
i
1
1
B  a B
1
2 2
…………….
B p−1 a B
p
p
B 
p
де B , B , … - це нові нетермінали граматики G . Очевидно,
1
2
1
що граматика G буде еквівалентна граматиці G.
1
19