Замечания. Задача 1. Если задана некоторая грамматика G, то возникает вопрос: какой язык порождает G?

Задача 1. Если задана некоторая грамматика G, то возникает вопрос: какой язык порождает G?

Пример:

G= {V, N, S, R}, V= {a, b, c}, N= {A, B, S},

R: bA®abc; aS®bAc; S®caS;bAB®ab.

Вывод начинается с символа S – начального символа грамматики:

S

caS

(ca)²S

(ca)³S

…

(ca)ⁿS= (ca)^n-1c aS

(ca)^n-1c bA c

(ca)^n-1cabcc= (ca)ⁿbcc

Таким образом, данная грамматика порождает язык L(G)= {a| a= (ca)ⁿbcc}.

Определение: Две грамматики называют эквивалентными, если они порождают один и тот же язык.

Если из рассмотренной грамматики исключить последнее правило, то получим эквивалентную ей грамматику.

Задача 2. Пусть задан некоторый язык. Построить грамматику, порождающую данный язык.

L= {aab, babaa, ababab}

R₁: S®aab, S®babaa, S®ababab; G₁= {{a, b}, {S}, S, R₁}

R₂: S®aA; S® BBa; S®AAA; A®ab;B®ba; G₂= {{a,b}, {S, A, B}, S, R₂}.

Вопросы и упражнения

1. Дана грамматика G= (Т, N, S, R), Т= {a, b, c, d}, N= {A, B, S},

R₀: S®aSc

bAB®ab

bAd®abc

aS®bAdc

Какой язык порождает данная грамматика?

Построить эквивалентную ей грамматику.

2. Построить нетривиальную грамматику, порождающую следующий язык:

L={abcda, abcaba, daabc, aabdaa, cada}. Докажите, что построенная Вами грамматика действительно порождает этот язык.