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

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

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

Рубрика: 

Язык L над алфавитом Σ представляет собой множество цепочек над Σ. Необходимо
различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={ε}≠0.
Формальный язык L над алфавитом Σ - это язык, выделенный с помощью конечного
множества некоторых формальных правил.
Пусть M и L - языки над алфавитами. Тогда конкатенация LM = {xyx∈L, y∈M}. В
частности, {ε}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 - начальный символ (аксиома грамматики), S∈V
N.
Из терминальных символов состоят цепочки языка, порожденного грамматикой.
Аксиомой называется символ в левой части первого правила вывода грамматики.
Для того чтобы различать терминальные и нетерминальные символы, принято
обозначать терминальные символы строчными, а нетерминальные символы заглавными
буквами латинского алфавита.
В грамматике G цепочка х непосредственно порождает цепочку у, если х = αuβ, у = αvβ
и u→v ∈ Р, т.е. цепочка у непосредственно выводится из х, что обозначается х => у.
Языком, порождаемым грамматикой 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}.
Говоря о представлении грамматик, нужно отметить, что множество правил вывода
грамматики может приводиться без специального указания множеств терминалов и
нетерминалов. В таком случае обычно предполагается, что грамматика содержит в точности
те терминальные и нетерминальные символы, которые встречаются в правилах вывода. 
    Язык L над алфавитом Σ представляет собой множество цепочек над Σ. Необходимо
различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={ε}≠0.
    Формальный язык L над алфавитом Σ - это язык, выделенный с помощью конечного
множества некоторых формальных правил.
    Пусть M и L - языки над алфавитами. Тогда конкатенация LM = {xyx∈L, y∈M}. В
частности, {ε}L = L{ε}=L. Используя понятие произведения, определим итерацию L* и
усеченную итерацию L+ множества L:
           ∞
   L+ =   UL ,   i

          i =1
           ∞
   L* =   UL ,   i

          i =1
   где i - степень языка, L определяется рекурсивно следующим образом:
   L0 = {ε};
   L1 = L;
   Ln+1 = Ln L = L Ln;
   {ε}L=L{ε}=L.
   Например, если задан язык L={a}, тогда L*={ε, а, аа, ааа, …}, L+={a, aa, aaa, …}.
   Порождающая грамматика - это упорядоченная четверка G= (VT, VN, P, S), где
   VT - конечный алфавит, определяющий множество терминальных символов;
   VN - конечный алфавит, определяющий множество нетерминальных символов;
   Р - конечное множество правил вывода, т.е. множество пар следующего вида:
                                    u → v,    где u, v ∈(VT∪VN)*;
   S - начальный символ (аксиома грамматики), S∈VN.
    Из терминальных символов состоят цепочки языка, порожденного грамматикой.
Аксиомой называется символ в левой части первого правила вывода грамматики.
    Для того чтобы различать терминальные и нетерминальные символы, принято
обозначать терминальные символы строчными, а нетерминальные символы заглавными
буквами латинского алфавита.
    В грамматике G цепочка х непосредственно порождает цепочку у, если х = αuβ, у = αvβ
и u→v ∈ Р, т.е. цепочка у непосредственно выводится из х, что обозначается х => у.
    Языком, порождаемым грамматикой G = (VT, VN, Р, S), называется множество
терминальных цепочек, выводимых в грамматике G из аксиомы:
    L(G) = {х | х ∈ VT*; S => *х}, где =>*- выводимость.
    Пример. Дана грамматика G = (VT, VN, Р, S), в которой VT = {а, b}, VN = {S}, Р = {S →
aSb, S → ab). Определить язык, порождаемый этой грамматикой.
    Решение. Используя рекурсию, выведем несколько цепочек языка, порождаемого данной
грамматикой:

   S → ab;
   S → aSb => aabb;
   S → aSb =>aaSbb => aaabbb; . . .

    Определим язык, порожденный данной грамматикой:
    L(G) = {anbn | n > 0}.
    Говоря о представлении грамматик, нужно отметить, что множество правил вывода
грамматики может приводиться без специального указания множеств терминалов и
нетерминалов. В таком случае обычно предполагается, что грамматика содержит в точности
те терминальные и нетерминальные символы, которые встречаются в правилах вывода.

Страницы