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

UptoLike

ВУЗ: 

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

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

Рубрика: 

16
Другими словами, язык есть множество терминальных цепочек,
выводимых из
начального нетерминала грамматики.
Определение 2.5. Любая цепочка α, такая, что α∈V
*
и S
α, называется
сентенциальной формой.
Определение 2.6. Грамматики G
1
и G
2
называются эквивалентными, если
L(G
1
) = L(G
2
).
Пример 2.1. Рассмотрим грамматику G = (V
N
, V
T
, P, S), где V
N
= {S}, V
T
= {0, 1},
P = {S → 0S1, S → 01}.
Здесь
S — единственный нетерминал, он же — начальный; 0 и 1 —
терминалы; правил два:
S → 0S1 и S → 01.
Применив первое правило
n –1 раз, а затем второе правило, получим:
S 0S1 00S11 0
3
S1
3
... 0
n –1
S1
n –1
0
n
1
n
.
Здесь мы воспользовались обозначением
w
i
= w ... w, причём w
0
= ε.
Таким образом, эта грамматика порождает язык
L(G) = {0
n
1
n
n ≥ 1}.
Действительно, при использовании первого правила число символов
S остаётся
неизменным и равно 1. После применения второго правила число символов
S в
сентенциальной форме уменьшается на единицу. Поэтому после использования
правила
S → 01 в результирующей цепочке не останется ни одного символа S.
Так как оба правила имеют в левой части по одному символу
S, то единственно
возможный порядок их применения — сколько-то раз использовать первое
правило, а затем один раз использовать второе.
Этот пример грамматики очень прост: было почти очевидно, какие
предложения выводятся в ней. В общем случае определить, что порождается
данной грамматикой, бывает нелегко. Дадим более сложный пример.
Пример 2.2. Пусть G = (V
N
, V
T
, P, S), где V
N
= {S, B, C}, V
T
= {a, b, c},
P = {(1) S → aSBC, (2) S → aBC, (3) CB → BC,
(4) aB → ab, (5) bB → bb, (6) bC → bc, (7) cC → cc}.
Язык
L(G) содержит цепочки вида a
n
b
n
c
n
для каждого n ≥ 1, так как мы
можем использовать правило (1)
n –1 раз, чтобы получить S
a
n –1
S(BC)
n –1
.
Затем мы используем правило (2), чтобы получить
S a
n
(BC)
n
. Правило (3)
даёт нам возможность расположить
B и C так, чтобы все B предшествовали
всем
C. Таким образом, S a
n
B
n
C
n
.
Далее мы используем один раз правило (4) и получаем
S a
n
bB
n–1
C
n
.
Затем, используя правило (5)
n –1 раз, получаем S a
n
b
n
C
n
.
Применив один раз правило (6), получим
S a
n
b
n
сC
n–1
.
Наконец, применив
n –1 раз правило (7), окончательно получим
S a
n
b
n
с
n
.
Легко показать, что в общем случае возможен только такой порядок
применения правил, т.е. что
L(G) = {a
n
b
n
с
n
n ≥ 1}.
i раз
*
G
⇒
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒
*
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒

Страницы