Формальні мови та їх завдання

v  G w, якщо v = x1 u x2 , w = x1 y x2 , u  y  P.

При цьому кажуть, що w безпосередньо виводиться з v застосуванням продукції u y. Наприклад, у граматиці G1 із прикладу 21.3 BC aC застосуванням продукції B a, aC a1застосуванням C 1.

2. На множині (X N)* означається відношення виводимості, позначене  *G (або  *, коли відомо, якою саме є G): v *w, якщо v=w або існує послідовність w1, w2, … , wn слів, де n 1, така, що v w1, w1 w2, … , wn-1 wn, wn=w. Так, у граматиці G1 BC *a1, оскільки BC aC, aC a1. Послідовність v w1 w2 … wn називається виведенням wn із v, а n – довжиною виведення. Інколи довжину записують замість '*' таким чином: v nw, наприклад, BC  2a1.

3. Якщо S G*w, то послідовність S … w називається виведенням слова w у граматиці G, а слово w – вивідним. Так, слова A, BC, aC, a1 вивідні в граматиці G1.

4. Вивідні слова в алфавіті X називаються породжуваними, а множина їх усіх – мовою, що задається (породжується) граматикою G: L(G) = {w | w X* та S  * w }.

Приклади

4. Граматика G1 із прикладу 21.3 задає мову { a, a1, a2 }.

5. Граматика

G2 = ( { a, …, z, 0, …, 9 }, { I, L, D },

{ I  L | IL | ID, L  a | … | z, D  0 | ... | 9 },

I )

породжує множину ідентифікаторів.

6. Граматика G3 = ( { (, ) }, { S }, { S   | ( S ) }, S ) задає множину "вкладених дужок" { (n)n | n  0 }.

7. Граматика

G4 = ( { a, b, c }, { S, A, B, C},

{ S  aSBC | abC, CB  BC, bB  bb, bC  bc, cC  cc },

S )

визначає мову { anbncn | n  1 }.

Граматики називаються еквівалентними, якщо задають ту саму мову. Наприклад, граматика

( { a, 1, 2 }, { A }, { A  a [ 1 | 2 ] }, A )

еквівалентна граматиці G1, граматика

( {a, …, z, 0, …, 9}, {I, C}, {I  (a|…|z)C, C   |C(a |…|z|0|…|9)}, I )