3. Izvođenje i transformiranje gramatika

1. IZVOÐENJE GRAMATIKA
2. TRANSFORMIRANJE GRAMATIKA
   • Supstitucija
   • Faktorizacija
   • Izbacivanje neupotrebljivih simbola
   • Izbacivanje ε-produkcija
   • Izbacivanje jediničnih produkcija
   • Chomskyjeva normalna forma (CNF)
   • Eliminiranje rekurzija slijeva
   • Greibachova normalna forma (GNF)
3. Pitanja i zadaci

I ovo je poglavlje posvećeno gramatikama. Prvi, "empirijski" dio, bavi se pokušajem dobivanja odgovora na pitanje: Kako za dani jezik izvesti odgovarajuću gramatiku? U drugom dijelu poglavlja, polazeći od pretpostavke da smo izveli kakvu-takvu gramatiku nekog jezika, dani su postupci transformiranja gramatike u jednostavniji oblik, a ponekad i u zadani oblik ili "formu".

3.1 IZVOÐENJE GRAMATIKA

Primjer 3.1

Izvedimo gramatiku jezika {aⁿbⁿ:   n≥l}. Prvo, ab je u jeziku, pa se može napisati:

S → ab

Sljedeća je rečenica aabb, gdje smo s ab označili prvu rečenicu. Ta se rečenica dobila dopisujući na početak prve rečenice znak a, na kraj znak b. Treća je rečenica aaabbb, dobila se istom operacijom, ali primijenjenoj na drugu rečenicu, itd. Dakle, ako je α rečenica, tada je i aαb takoðer rečenica, a to je "klasični" primjer rekurzije, pa je gramatika danog jezika:

S → ab | aSb

Primjer 3.2

No, izvoðenje gramatike jezika {aⁿbⁿcⁿ: n≥l} sigurno je složenije. Započet ćemo najjednostavnijom rečenicom: abc koja nam daje produkciju:

(1)S → abc

Iduća je rečenica aabbcc. Ne možemo je izravno dobiti iz prve. Ideja je da se krene slijeva i ispred prvog b u abc umetne ponovo abc, pa imamo aabcbc, a to je nova alternativa:

(2)S → aSQ

Iz niza izvoðenja

     S => aSQ => aabcQ

bolje se vidi značenje novo uvedenog simbola Q. On mora biti zamijenjen na neki način s bc, a to se može postići ovako:

cQ → Qc

bQc → bbcc

Dakle, gramatika s produkcijama:

S → abc | aSQ

bQc → bbcc

cQ → Qc

generira jezik {aⁿbⁿcⁿ: n≥l}. Na primjer:

S => aSQ => aaSQQ => aaaSQQQ    => aaaabcQQQ

  => aaaabQcQ     => aaaabbccQQ => aaaabbcQcQ

  => aaaabbQccQ   => aaaabbbcccQ => aaaabbbccQc

  =>  aaaabbbcQcc => aaaabbbQccc => aaaabbbbcccc

Primjer 3.3

Izvedimo gramatiku jezika prirodnih brojeva {1,2,3, . . .}. Prvo, 1, 2, ..., 9 su u jeziku:

N → B

B → 1| 2| 3| 4| 5| 6| 7| 8| 9

Drugo, ako prirodni broj ima više od jedne znamenke, mora započeti s B, potom slijedi niz znamenki, npr. C

N → BC

C → B| 0| CC| ε

Primijetiti da se umjesto ove dvije produkcije u proširenom BNF-u može napisati:

N → B{C}

C → B| 0

Sada ne bi bio problem izvesti gramatike jezika parnih ili neparnih prirodnih brojeva, što vam ostavljamo za vježbu.

Primjer 3.4

Izvedimo gramatiku jezika {4,8,12,16,20/...}, tj. jezika koji sadrži prirodne brojeve djeljive s četiri. U matematici smo naučili da su to brojevi 4 i 8, odnosno, ako broj ima više od jedne znamenke, djeljiv je s četiri ako je broj sačinjen od njegove dvije posljednje znamenke djeljiv s četiri ili se završava s 00. Na primjer, u jeziku su nizovi 20, 1004, 12345678900 ili 101010196. Dakle, na najvišoj razini, možemo definirati gramatiku:

S → 4| 8| D| NE

gdje je N prirodni broj kako je definirano u primjeru 3.3, D predstavlja sve dvoznamenkaste brojeve djeljive sa četiri:

D → PX| QY

P → 1| 3| 5| 7| 9

X → 2| 6

Q → 2| 4| 6| 8

Y → 0| 4| 8

a E je:

E → 0Y| D

na primjer, rečenica 1004 može se izvesti u nizu izvoðenja:

S => NE => BCE => 10E => 100Y => 1004

Primjer 3.5

A sada pokušajmo izvesti gramatiku jezika {3, 6, 9,12,15,18, . . .}, tj. jezika koji sadrži prirodne brojeve djeljive s 3. Znamo da je broj djeljiv s 3 ako je zbroj njegovih znamenki djeljiv s 3. Ali, kako u produkcijama beskontekstne gramatike zadovoljiti taj uvjet? Je li to moguće, kad znamo da u gramatici nisu definirane nikakve operacije?!

Dakako, iz promatranja beskonačnog skupa jezika brojeva djeljivih s 3 ne bismo mogli doći do rješenja. No, pokušajmo razmišljati ovako: ako je broj djeljiv s 3, zbroj ostataka dijeljenja svih njegovih znamenki s 3 jednak je nula ili je neki broj koji je takoðer djeljiv s 3. To, na primjer, znači da ako broj započinje s 1, 4 ili 7 (ostatak dijeljenja s 3 jednak je 1), drugi dio broja mora sadržavati znamenku čiji je ostatak dijeljenja s tri jednak 2 (a to su 2, 5 ili 8) ili dvije znamenke čiji je ostatak dijeljenja jednak 1. Na primjer, brojevi 18, 111 ili 147 djeljivi su s 3. Dakle, na najvišoj razini, možemo definirati gramatiku:

S → AB| BA| C

gdje A predstavlja niz brojki od kojih je zbroj ostataka dijeljenja s 3 jednak 1, B niz brojki od kojih je zbroj ostataka dijeljenja s 3 jednak 2, a C niz brojeva koji počinju s 3, 6, ili 9. Dalje je:

A → 1| 4| 7

B → 2| 5| 8| BX| AA

A → 1| 4| 7| AX| BB

Na kraju, kompletna gramatika koja generira brojeve djeljive s 3 je:

S → AB| BA| C

A → 1| 4| 7| AX| BB

B → 2| 5| 8| BX| AA

C → Y| CX| CS

X → 0| Y| XS

Y → 3| 6| 9

Na primjer, rečenice 1200, 2322543 i 111 može se izvesti u nizu izvoðenja:

S => AB => 1B => 1BX => 1BXX => 12XX => 120X => 1200

S => BA => BXA => 2XA => 2YA => 23A => 23BB => 232B

  => 232AA => 232BBA => 2322BA => 23225A => 23225AX

  => 2322254X => 232254Y => 2322543

S => AB => 1B => 1AA => 11A => 111

3.2. TRANSFORMIRANJE GRAMATIKA

Definicija 3.1

Kaže se da su dvije gramatike, G₁ i G₂, ekvivalentne ako je ispunjen uvjet:

L(G₁) = L(G₂)

Supstitucija

S → 0A1

OA → 00A1

A → ε

L(G₁) = {01, 0011,000111,... } = {0ⁿlⁿ: n≥1}

B → 0A

S → BI

B → OBI

B → 0A

A → ε

S → B1

B → OB1 | 0

To nije sve. Promatrajući jezik koji gramatike G₁, G₂ i G₃ generiraju, može se izvesti gramatika G₄ (primjer 3.1, samo umjesto terminala a i b imamo 0 i 1) s produkcijama:

S → 01 | OSI

Faktorizacija

S → (0 | OS) 1

S → X1

X → 0 | OS

Dalje se produkcija za X može faktorizirati slijeva:

X → 0 (ε | S)

S → X1

X → 0Y

Y → ε | S

Izbacivanje neupotrebljivih simbola

S → aba

A → c

Definicija 3.2

Kaže se daje simbol XεNUT neupotrebljiv u beskontekstnoj gramatici G={N, T, P, S) ako ne postoji izvoðenje S^*=>;wXy^*=>wxy, gdje su w,x,y &epsilon T^*.

Algoritam 3.1

Je li L(G) neprazan?

Ulaz

Beskontekstna gramatika G=( N,T,P,S).

Izlaz

"Da" ako je L(G)≠Ø, "ne" inače.

Postupak

Izgrade se skupovi N_o, N_i, ... rekurzivno, kao što slijedi:

1. Neka je N_o≠Ø i i=l.
2. Neka je N_i={A: A →α je u P, αε (N_i-1UT *}U N_i-1
3. Ako je N_i≠N_i-1, tada i=i+l, ide se na korak (2). Inače, N_e=N_i
4. Ako je SεN_e, ispisati "da", inače ispisati "ne".

Budući da je N_ecN, postupak će se završiti poslije najviše n+1 koraka.

Definicija 3.3

Kaže se da je simbol XεNUT nedokučiv u beskontekstnoj gramatici G=( N,T,P,S) ako se X ne pojavljuje niti u jednoj rečeničnoj formi.

Algoritam 3.2

Izbacivanje nedokučivih simbola.

Ulaz

Beskontekstna gramatika G=( N,T,P,S).

Izlaz

Ekvivalentna gramatika G'=(N',T',P',S') tako da je L(G)=L(G') i za svaki XεN'UT' postoje αßε(N'UT' )* tako da je S*=>αXß u G' .

Postupak

1. V_o{S}, i=l.
2. V_i={X: (A→ αXß) ε P ^ AεV_i-1}UV_i-1.
3. Ako je V_i≠V_i-1, i=i+l i ide se na korak (2). Inače:

N' = V_i∩N

T' = V_i∩T

P' će biti one produkcije iz P koje sadrže samo simbole iz V_i

G' = (N',T',P',S')

Algoritam 3.3

Izbacivanje neupotrebljivih simbola.

Ulaz

Beskontekstna gramatika G=(N, T, P, S), tako da je L(G)≠Ø.

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S') tako da je L(G) = L'(G'), i ne postoji nijedan neupotrebljiv simbol u N'UT'.

Postupak

(1) Upotrijebiti algoritam 3.1 da bi se dobio skup N_e. Tada je gramatika G₁=(N≠N_e,T,P₁, S), gdje P₁ sadrži samo one produkcije iz P koje uključuju simbole iz N_eUT.

(2) Primijeniti algoritam 3.2 na G₁ da bi se dobilo G' = (N',T',P',S')

Primjer 3.6

Neka je G= ({S,A,B},{a,b}, P, S), gdje je skup produkcija P.

S → a|A      A → AB      B → b

Primijenimo algoritam 3.3 na tu gramatiku. U koraku (1) je N_e={a,b}, tako da je G₁= ({S,B}, {a, b}, {S→a, B→b}, S). Dalje, primjenom algoritma 3.2, dobili bismo V₂=V₁={S, a}. Dakle, G' = ({S}, {a}, {S→}, S).

Da smo prvo upotrijebili algoritam 3.2 na gramatiku G zaključili bismo da su svi simboli dokučivi, pa bi gramatika ostala nepromijenjena. Primjenom potom algoritma 3.1, dobili bismo N_e={S,B} tako da bi rezultirajuća gramatika bila G_i, a ne G'.

Izbacivanje ε-produkcija

Definicija 3.4

Kaže se da je gramatika G= (N, T, P, S) bez ε-produkcija ako

(1) P ne sadrži produkcije, ili

(2) Postoji samo jedna ε-produkcija S→ε i S se ne pojavljuje niti u jednoj alternativi (desnoj strani) ostalih produkcija iz P.

Algoritam 3.4

Izbacivanje ε-produkcija.

Ulaz

Beskontekstna gramatika G=(N, T, P, S)

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S').

Postupak

(1) Izgraditi N_e={A: AeN i A⁺=>ε} slično kao u algoritmu 3.1.

{2) Neka je P' skup produkcija izgraðen na sljedeći način:

    (a) Ako je A→α_oB₁α₁B₂...B_kα_k u P, k≥0, i za l≥i≥k svaki B_i je u N_e, ali nijedan simbol iz α_j nije u N_e, 0≥j≥k, dodati u P' sve produkcije oblika:

A→α₁X₁α₁...B_kα_k

          gdje je X₁ ili B₁ ili ε, bez dodavanja A→ε u P'(to će se dogoditi ako su svi α_i=ε ).

    (b)Ako je SeN_e, dodati u P' produkcije:

S'→&epsilon|S

          gdje je S' novi (početni) simbol i N'=NU{S'}. Inače je N'=N i S' =S.

(3) Nova ekvivalentna gramatika je G'=(N', T', P', S').

Primjer 3.7

Primijenimo algoritam 3.4. na gramatiku G s produkcijama:

S → aSbS | bSaS | ε

Konačno će se dobiti gramatika G' s produkcijama:

S'→S| ε          S →aSbS| bSaS| aSb| abS| ab| bSa| baS| ba

Izbacivanje jediničnih produkcija

Algoritam 3.5

Izbacivanje jediničnih produkcija.

Ulaz

Beskontekstna gramatika G=(N, T, P, S) bez ε-produkcija.

Izlaz

Ekvivalentna beskontekstna gramatika G' bez jediničnih produkcija i bez ε-produkcija.

Postupak

(1)Izgraditi za svaki A iz N skup N_A={B: A*=>B} na sljedeći način:

(a)N_o={A}, i=l.

(b)N_i={C: (B→C)e P ^ BeN_i-1}UN_1-i.

(c)Ako je N_i≠N_1-i, i=i+l i ide se na korak (b). Inače, N_A=N_i.

(2) Izgraditi P' tako da ako je B→α u P i nije jedinična produkcija, produkcijama P' dodati sve A→α za koje jeBeN_A.

(3) Nova ekvivalentna gramatika je G'=(N', T', P', S').

Primjer 3.8

Primijenimo algoritam 3.5. na gramatiku G s produkcijama

E → E+T | T

T → T*F | F

F → (E) | a

U koraku (1) je N_e={E,T,F}, N_T={T,F}, N_F={F}. Poslije koraka (2), P' postaje:

E → E+T | T*F | (E) | a

T → T*F | (E) | a

F → (E) | a

Definicija 3.5

Beskontekstna gramatika G je svojstvena (engl. proper) ako nema produkcija A→ε i nema petlji, tj. ne postoji niz izvoðenja A⁺=>A.

Chomskyjeva normalna forma (CNF)

Definicija 3.6

Kaže se da je gramatika G=(N, T, P, S) u Chomskvjevoj normalnoj formi (CNF) ako je svaka produkcija u Poblika:

(1) A→BC, A,B,CeN, ili

(2) A→a, aeT, ili

           (3) Ako je ε u jeziku L=(G), tada je S→ε i S se ne pojavljuje niti u jednoj alternativi (desnoj strani) ostalih produkcija iz P.

Algoritam 3.6

Konverzija u CNF.

Ulaz

Svojstvena beskontekstna gramatika G=(N, T, P, S).

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S') u CNF.

Postupak

Skup produkcija P' izgraditi na sljedeći način:

(1)Dodati sve produkcije iz P oblika A→a u P'.

(2)Dodati sve produkcije iz P oblika A→BC u P'.

(3)Ako je S→ε u P dodati S→ε skupu produkcija P' <P'.

(4)Za sve produkcije oblika A→X_i. . .x_k iz P, k≥2, iz P dodati u P' sljedeći skup produkcija. Neka X'_i stoji za X_i, X_ieNUT, i X'_i je novi neterminal ako je X_iT. Preureðene produkcije su:

           A   → X'_i<X₂...X_k>

    <X₂... X_k>  → X'₂<X₃... X_k

   <X_k-2... X_k> → X'_k-2<X_k-1X_k>;

   <X_k-1... X_k> → X'_k-1X'_k

gdje je svaki <X_i...X_k> novi neterminal.

(5)Za sve produkcije oblika A→X₁X₂ iz P, gdje je X₁eT v X₂eT dodati u P' produkciju A→X'₁X'₂.

(6)Za svaki neterminal oblika a', uvedenog u koracima (4) i (5), dodati u produkciju a'→a. Konačno, skup neterminala N' je skup N kojem su dodani svi novouvedeni neterminali, pa je gramatika u CNF.

Primjer 3.9

Primijenimo algoritam 3.6 na gramatiku G s produkcijama

S → aAB | BA

A → BBB | a

B → AS | b

Najprije se, prema koracima (1) i (2) u P' mogu prenijeti produkcije:

S → BA

A → a

B → AS | b

Zatim zamjenjujemo S→aAB s S→a'<AB> i <AB> s <AB>→AB. Potom je zamijenjeno A→BBB s A→B<BB> i <BB> s <BB>→BB. Konačno, u P' se dodaje produkcija a'→a, pa je rezultirajuća gramatika sa skupom produkcija P':

   S → a'<AB> | BA

   A → B<BB> | a

   B → AS | b

<AB> → AB

<BB> → BB

  a' → a

Ako uvedemo supstituciju X za a', Y za <AB> i Z za <BB>, s ciljem da neterminale prikažemo samo jednim slovom, dobili bismo pregledniju gramatiku:

S → XY | BA

A → BZ | a

B → AS | b

Y → AB

Z → BB

X → a

Eliminiranje rekurzija slijeva

Teorem 3.1

Svaki beskontekstni jezik ima gramatiku nerekurzivnu slijeva.

Teorem 3.2

Ako je G gramatika G=(N, T, P, S) u kojoj su:

A → Aα₁|...|Aα_m|ß₁|...|ß_n

sve A-produkcije u P i nijedan ß_i ne počinje s A, tada je G'gramatika ekvivalentna gramatici G, G'= (NU{A'}, T, P', S), gdje je A' novi neterminal, a P' je dobiveno iz P u kojem su produkcije zamijenjene sa:

A → ß₁|...|ß_n|ß₁A'|...|ß_nA'

A' → α₁|...|α_m|α₁A'|...α|_mA'

Primjer 3.9

Primijenimo transformaciju iz teorema 3.2. na gramatiku G s produkcijama:

E → E + T | T

T → T*F | F

F → (E) | a

Dobit ćemo gramatiku G' s produkcijama:

E →  T   | TE'

E'→ +T   |+TE'

T → F    | FT'

T'→ *F   |*FT'

F → (E)  |a

odnosno, ako E' zamijenimo s X, a T' s Y, imamo:

E →  T   | TX

X → +T   |+TX

T →  F   | FY

Y → *F   |*FY

F → (E)  |a

Algoritam 3.7

Eliminiranje rekurzija slijeva.

Ulaz

Svojstvena beskontekstna gramatika G=(N, T, P, S).

Izlaz

Ekvivalentna gramatika G'=(N', T', P', S') nerekurzivna slijeva.

Postupak

Teorem 3.2 je temeljni za eliminiranje rekurzija slijeva. Skup produkcija P' izgraditi na sljedeći način:

(l)Neka je N={A₁, . . ., A_n}. Treba transformirati G tako da ako je A_i→α produkcija, tada α počinje ili terminalom ili neterminalom A_j tako da je j>i. Postaviti i=l.

(2)Neka je A_i-produkcija oblika A_i→A_iα_i|...|A_iα_m|ßi|...|ß_p gdje nijedan ß_j ne počinje s A_k ako je k≤i. (Uvijek će to biti moguće.) Zamijeniti A_i-produkcije sa:

A₁ → ß₁|...|ß_p|ß₁A'_i|...|ß_pA'_i

A'₁ → α₁|...|α_m|α₁A'_i|...|α_mA'_i

gdje je A'_i novi neterminal. Sada sve A_i-produkcije počinju terminalom ili s A_k, k>i.

(3)Ako je i=n, G' će biti rezultirajuća gramatika i prekida se daljnje izvoðenje postupka. Inače, i=i+l i j=l.

(4)Zamijeniti sve produkcije oblika A_i→A_jα, gdje je A_j→ß₁|...|ß_m, produkcijama A_i→ß₁α|...|ß_mα. Ako je A_j-produkcija počinjala terminalom ili s A_k, k>j, isto svojstvo će sada imati A_i-produkcija.

(5) Ako je j=i-l, ide se na korak (2). Inače, j=j + l i ide se na korak (4).

Primjer 3.10

Primijenimo algoritam 3.7 na gramatiku G s produkcijama:

A → BC | a

B → CA | Ab

C → AB | CC | a

Odmah uočavamo da je C-produkcija rekurzivna slijeva, dok A i B imaju skrivene rekurzije, takoðer slijeva. Neka je A₁=A, A₂=B i A₃=C. Prikazana je promjena gramatika poslije svake primjene koraka (2) ili (4), ali samo nove produkcije neterminala čije su produkcije promijenjene:

(2), i=l:             nema promjene

(4), i=2, j=l: B → CA|BCb|ab

(2), i=2:             B → CA|ab|CAB'|abB'

                      B'→ CbB*|Cb

(4), i=3, j=l: C → BCB|aB|CC|a

(4), i=3, j=2: C → CACB|abCB|CAB'CB|abB'CB|aB|CC|a

(2), i=3:          C → abCB|abB'CB|aB|a|abCBC'|abB'CBC' |aBC'|aC

                  C' → ACBC'|AB'CBC'|CC'|ACB|AB'CB|C

Konačno, uvodeći smjenu X za B' i Y za C', rezultirajuća gramatika bez rekurzija slijeva ima produkcije:

A → BC | a

B → CA | ab | CAX | abX

X → CbX | Cb

C → abCB | abXCB | aB | a | abCBY | abXCBY | aBY | aY

Y → ACBY | AXCBY | CY | ACB | AXCB | C

Greibachova normalna forma (GNF)

Definicija 3.7

Kaže se da je gramatika G=(N, T, P, S) u Greibachovoj normalnoj formi (GNF) ako je G bez ε-produkcija i ako je svaka produkcija iz P oblika:

A → aα    aeT,     αeN^*

Algoritam 3.8

Konverzija gramatike u Greibachovu normalnu formu (GNF).

Ulaz

Svojstvena beskontekstna gramatika G=(N, T, P, S) koja nije rekurzivna slijeva.

Izlaz

Ekvivalentna gramatika G'=(N', T, P', S) u Greibachovoj normalnoj formi.

Postupak

(1) Linearno urediti skup neterminala, N={A₁,..., A_n} tako da vrijedi:

A₁<A₂<...<A_n

(2) i = n - 1

(3) Ako je i=0 ide se na korak (5). Inače, zamijeniti svaku produkciju oblika A_i→A_jα, j>i, s A_i→ß₁α|...|ß_mα, gdje je A_j→ß₁|...|ß_m, tj. ß_k su sve alternative od A_j koje počinju terminalom.

(4) i = i - 1 i vraća se na korak (3).

(5) Sada sve produkcije (osim S→ε, ako postoji) počinju terminalom. U svakoj produkciji, A→aX₁...X_k, treba zamijeniti X_j, ako je terminal, s X'_j, gdje je X'_j novi neterminal.

(6) Za sve X'j uvedene u koraku (5) dodati produkciju X'_j→X_j.

Primjer 3. 11

Transformirajmo rezultirajuću gramatiku iz primjera 3.9 u GNF:

E →  T   | TX

X → +T   |+TX

T →  F   | FY

Y → *F   |*FY

F → (E)  |a

Prvo uvedimo linearno ureðenje na skupu neterminala: X<E<Y<T<F. Neterminal F je najveći u tom ureðenju i sve njegove alternative počinju terminalom. T je sljedeći simbol s produkcijama T→F|FY, tako da se F supstituira sa svojim alternativama, pa se dobije:

T → (E)|a|(E)Y|aY

Sada je Y na redu, ali sve njegove alternative počinju terminalom pa nema promjena. Slijedi zamjena E-produkcija sa:

E → (E)| a| (E)Y| aY| (E)X| aX| (E)YX| aYX

X-produkcije započinju terminalom pa nije potrebna transformacija. Koraci (5) i (6) uvode novi neterminal ) ' i produkciju:

) ' → )

Na svim mjestima pojavljivanja terminala ) treba stajati )', no mi ćemo, opet radi preglednosti, umjesto ) pisati Z, pa je rezultirajuća gramatika u Greibachovoj normalnoj formi:

E → (EZ| a | (EZY | aY | (EZX | aX | (EZYX | aYX

X → +T| +TX

T → (EZ | a | (EZY | aY

Y → *F | *FY

F → (E) | a

Z → )

Pitanja i zadaci

S → B1         B → OB1 | 0

može transformirati u ekvivalentnu gramatiku s produkcijama

S → 01 | OS1

S → ABC              A → BB | ε

B → CC | a           C → AA | b

S → A | B         A → C | D             B → D|E

C → S |a |ε       D → S | b             E → S | c | ε

a) S → OS1 | 01

b) S → aB | bA

  A → aS | bAA | a

  B → bS | aBB | b

S → Ba | Ab         A → Sa | AAb | a               B → Sb | BBa | b

Sadržaj