Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 26 стр.

UptoLike

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

Язык L над алфавитом Σ представляет собой множество цепочек над Σ. Необходимо
различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={ε}0.
Формальный язык L над алфавитом Σ - это язык, выделенный с помощью конечного
множества некоторых формальных правил.
Пусть M и L - языки над алфавитами. Тогда конкатенация LM = {xyxL, yM}. В
частности, {ε}L = L{ε}=L. Используя понятие произведения, определим итерацию L
*
и
усеченную итерацию L
+
множества L:
L
+
=
U
=
1i
i
L ,
L
*
=
U
=
1i
i
L ,
где i - степень языка, L определяется рекурсивно следующим образом:
L
0
= {ε};
L
1
= L;
L
n+1
= L
n
L = L L
n
;
{ε}L=L{ε}=L.
Например, если задан язык L={a}, тогда L
*
={ε, а, аа, ааа, …}, L
+
={a, aa, aaa, …}.
Порождающая грамматика - это упорядоченная четверка G= (V
T,
V
N,
P, S), где
V
T
- конечный алфавит, определяющий множество терминальных символов;
V
N
- конечный алфавит, определяющий множество нетерминальных символов;
Р - конечное множество правил вывода, т.е. множество пар следующего вида:
u v, где u, v (V
T
V
N
)*;
S - начальный символ (аксиома грамматики), SV
N.
Из терминальных символов состоят цепочки языка, порожденного грамматикой.
Аксиомой называется символ в левой части первого правила вывода грамматики.
Для того чтобы различать терминальные и нетерминальные символы, принято
обозначать терминальные символы строчными, а нетерминальные символы заглавными
буквами латинского алфавита.
В грамматике G цепочка х непосредственно порождает цепочку у, если х = αuβ, у = αvβ
и uv Р, т.е. цепочка у непосредственно выводится из х, что обозначается х => у.
Языком, порождаемым грамматикой G = (V
T
, V
N
, Р, S), называется множество
терминальных цепочек, выводимых в грамматике G из аксиомы:
L(G) = {х | х V
T
*; S => *х}, где =>*- выводимость.
Пример. Дана грамматика G = (V
T
, V
N
, Р, S), в которой V
T
= {а, b}, V
N
= {S}, Р = {S
aSb, S ab). Определить язык, порождаемый этой грамматикой.
Решение. Используя рекурсию, выведем несколько цепочек языка, порождаемого данной
грамматикой:
S ab;
S aSb => aabb;
S aSb =>aaSbb => aaabbb; . . .
Определим язык, порожденный данной грамматикой:
L(G) = {a
n
b
n
| n > 0}.
Говоря о представлении грамматик, нужно отметить, что множество правил вывода
грамматики может приводиться без специального указания множеств терминалов и
нетерминалов. В таком случае обычно предполагается, что грамматика содержит в точности
те терминальные и нетерминальные символы, которые встречаются в правилах вывода.