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

UptoLike

ВУЗ: 

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

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

Рубрика: 

15
Определение 2.1. Грамматикой называется четверка G = (V
N
, V
T
, P, S), где
V
N
, V
T
— алфавиты (словари) нетерминалов и терминалов соответственно,
причём
V
N
∩ V
T
= ∅, P — конечное множество правил, каждое из которых
имеет вид
α → β, где α∈ V
*
V
N
V
*
, β∈ V
*
, V = V
N
∪ V
T
— объединённый алфавит
(
словарь) грамматики; S — начальный нетерминал.
В дальнейшем нетерминалы мы будем обозначать заглавными латинскими
буквами, например S, A, B, C; терминалы — строчными буквами из начала
латинского алфавита, например,
a, b, c; цепочки терминалов — строчными
буквами из конца латинского алфавита, например
x, y, z; цепочки символов из
объединённого алфавита — строчными греческими буквами, например α, β, γ.
Мы представили грамматику
G = (V
N
, V
T
, P, S), но не определили язык,
который она порождает. Для этого нам потребуется ввести отношение
непосредственной выводимости , его транзитивное и рефлексивно-
транзитивное замыкание .
Когда очевидно, в какой грамматике производится вывод, имя грамматики
G под двойной стрелкой можно не указывать.
Определение 2.2. Пусть α→β∈ P — правило, γ, δ — любые цепочки из
множества
V
*
. Тогда γαδ γβδ читается следующим образом: “из γαδ
непосредственно выводится γβδ в грамматике G при помощи данного
правила”.
Другими словами, символ
связывает две цепочки тогда и только тогда,
когда вторая цепочка получается из первой применением единственного
правила.
Определение 2.3. Пусть α
1
, α
2
, ..., α
m
— цепочки из множества V
*
и α
1
α
2
,
α
2
α
3
, ..., α
m –1
α
m
. Тогда мы пишем α
1
α
m
и говорим, что “из α
1
выводится
α
m
в грамматике G”.
Другими словами, α
β, если β может быть получена из α путем
применения некоторого числа правил из множества правил
P. Считается, что
α
α для любой цепочки α∈ V
*
(рефлексивность) и для этого не требуется
никаких правил.
Если мы хотим подчеркнуть, что такой вывод использует по крайней мере
одно правило грамматики, то мы пишем
α
β. Если мы хотим указать, что
такой вывод происходит за
n шагов, т.е. посредством применения n правил
грамматики, то пишем
α
β. Значок
обозначает n-ю степень отношения
непосредственной выводимости.
Напомним,
что для любого отношения R имеют место следующие тождества:
R
0
= E ={(α, α)∀ α∈ V
*
}, R
n
= RR
n –1
= R
n –1
R для n > 0; в частности, R
1
= R;
*
=
= 0
k
k
k
R
R
∞
=
∪
,
=
= 1
.
k
k
k
R
R
+
∞
=
∪
Они, разумеется,
применимы и к отношению непосредственной выводи-
мости
.
Определение 2.4. Язык, порождаемый грамматикой G, определим как
L(G) = {ww∈ V
T
*
, }.
*
G
Sw⇒
G
+
⇒
*
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
G
⇒
*
G
⇒
*
G
⇒
G
⇒
G
+
⇒
n
G
⇒
n
G
⇒
G
⇒
*
G
⇒

Страницы