Pojednostavljenje gramatike

Pojednostavljenje gramatike je skupni naziv za postupke odbacivanja beskorisnih znakova i produkcija, odnosno za postupke transformacije zapisa gramatike u neki oblik pogodniji za obradu. Za danu formalnu gramatiku gradimo istovjetnu gramatiku (tj. gramatiku koja generira isti jezik) bez zalihosnih znakova i produkcija.

Odbacivanje znakova

Ako se znak X gramatike Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G=(V,T,P,S)} koristi u postupku generiranja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S\Rightarrow \alpha X\beta \Rightarrow w} , gdje su Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha ,\beta \in (V\cup T)*} i $w\in T*$ , onda je znak x koristan. U suprotnom, znak je beskoristan.

Dva su vida beskorisnosti: znak može biti mrtav ili nedohvatljiv, Ako iz znaka X nije moguće generirati niz završnih znakova, tj. ne postoji postupak generiranja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle X\Rightarrow w_{X}} , gdje je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{X}\in T*} , tada je znak X mrtav. Nije li znak mrtav, kaže se da je živ. Ako se znak X ne nalazi ni u jednom nizu koji se generira iz početnog nezavršnog znaka, tj. ne postoji postupak generiranja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S\Rightarrow \alpha X\beta } , tada je znak X nedohvatljiv.

Odbacivanje mrtvih znakova

Neka dana kontekstno neovisna gramatika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G=(V,T,P,S)} generira neprazni jezik, tj. $L(G)\neq \emptyset$ . Moguće je izgraditi istovjetnu gramatiku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G'=(V',T',P',S)} koja nema mrtvih znakova, odnosno za bilo koji Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\in V'} vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\Rightarrow w,w\in T*} .

Algoritam traženja živih znakova zasniva se na sljedećem svojstvu: Ako su živi svi znakovi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle X_{1},X_{2},...,X_{n}} desne strane produkcije

A\to X_{1}X_{2}...X_{n}

onda je živ i nezavršni znak A lijeve strane produkcije.

Algoritam traženja živih znakova izvodi se u tri koraka:

U listu živih znakova stave se lijeve strane produkcija koje na desnoj strani nemaju nezavršnih znakova.
Ako su na desnoj strani produkcije isključivo živi znakovi, onda se nezavršni znak lijeve strane produkcije doda u listu živih znakova.
Ako nije moguće proširiti listu živih znakova, algoritam se zaustavlja. Svi znakovi koji nisu u listi živih znakova su mrtvi znakovi.

Pseudokod opisanog algoritma jest sljedeći:

StaraListaŽivih = Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \emptyset }
;
NovaListaŽivih = Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ {A|A \to w} ,\mathrm{i\ }w \in T* \right\}}
;

dok (StaraListaŽivih Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ne}
 NovaListaŽivih)
{
  StaraListaŽivih = NovaListaŽivih;
  NovaListaŽivih = NovaListaŽivih Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \cup \left\{{A|A\to \alpha ,\alpha \in (T\cup StaraListaZivih)*}\right\}}
;
}

ListaŽivih = NovaListaŽivih;

Odbacivanje nedohvatljivih znakova

Moguće je izraditi gramatiku Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G' = (V',T',P',S)} koja je istovjetna kontekstno neovisnoj gramatici Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,T,P,S)} i koja nema nedohvatljivih znakova, tj. za bilo koji Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \in V' \cup T'} vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S\Rightarrow \alpha X\beta } , gdje je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha ,\beta \in (V'\cup T')*} .

Algoritam traženja dohvatljivih znakova zasniva se na sljedećem svojstvu:
Ako je dohvatljiv nezavršni znak A lijeve strane produkcije:

A\to \alpha _{1}|\alpha _{2}|...|\alpha _{n}

tada su dohvatljivi svi završni i nezavršni znakovi u nizovima Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha _{1}} , Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha _{2}} ... i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \alpha _{n}} desne strane produkcije.

Algoritam traženja dohvatljivih znakova izvodi se u tri koraka:

U listu dohvatljivih znakova stavi se početni nezavršni znak gramatike.
Ako je znak lijeve strane produkcije u listi dohvatljivih znakova, onda se svi znakovi desne strane produkcije dodaju u listu dohvatljivih znakova.
Ako listu dohvatljivih znakova nije moguće proširiti, algoritam se zaustavlja. Svi znakovi koji nisu u listi dohvatljivih znakova su nedohvatljivi.

Pseudokod opisanog algoritma jest sljedeći:

StaraListaDohvatljivih =  $\emptyset$ ;
NovaListaDohvatljivih = Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\{{S|S}\mathrm {\ je\ pocetni\ nezavrsni\ znak\ } \right\}}
;

dok (StaraListaDohvatljivih Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \neq }
 NovaListaNedohvatljivih)
{
  StaraListaDohvatljivih = NovaListaDohvatljivih;
  NovaListaDohvatljivih = StaraListaDohvatljivih Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \cup \left\{{X|X\mathrm {\ je\ u\ nizu\ } \alpha _{i},A\to \alpha _{i}\wedge A\in StaraListaDohvatljivih}\right\}}
;
}

ListaDohvatljivih = NovaListaDohvatljivih;

Odbacivanje beskorisnih znakova

Primjenom algoritma odbacivanja mrtvih znakova, a potom algoritma odbacivanja nedohvatljivih znakova, iz gramatike se odbacuju svi beskorisni znakovi. Primjena algoritma obrnutim redoslijedom neće nužno odbaciti sve beskorisne znakove, s obzirom da tad neki znakovi mogu ostati dohvatljivi primjenom mrtvih znakova.

Odbacivanje produkcija

Produkcije oblika $A\to B$ su jedinične produkcije. Sve ostale produkcije, uključujući i produkcije oblika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\to a} i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\to \epsilon } , nazivaju se nejedinične produkcije.

Produkcije oblika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\to \epsilon } nazivaju se $\epsilon$ -produkcije. Njihovo korištenje je moguće izbjeći ukoliko prazni niz nije element jezika kojeg gramatika generira.

Odbacivanje $\epsilon$ -produkcija

Neka gramatika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G=(V,T,P,S)} generira kontekstno neovisni jezik $L(G)-\left\{\varepsilon \right\}$ . Tada je moguće izgraditi istovjetnu gramatiku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G'=(V',T',P',S)} koja nema $\epsilon$ -produkcija.

Algoritam odbacivanja $\epsilon$ -produkcija se izvodi u dva osnovna koraka:

Pronađu se svi nezavršni znakovi koji generiraju prazni niz. Prazni znakovi su oni znakovi za koje vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\Rightarrow \epsilon } . Prazni se znakovi traže sljedećim iterativnim algoritmom:
1. U listu prazni znakova se stave lijeve strane svih $\epsilon$ -produkcija.
2. Ako su svi znakovi desne strane neke od produkcija zapisani u listu praznih znakova, tada se lista praznih znakova nadopuni lijevom stranom te produkcije.
3. Ako više nije moguće proširiti listu praznih znakova, algoritam se zaustavlja.
Skup produkcija gramatike Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G'} se gradi na sljedeći način. Ako je:
$A\to X_{1}X_{2}...X_{n}$
produkcija gramatike G, tada se u skup produkcija gramatike $G'$ dodaju produkcije oblika:
Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\to \xi _{1}\xi _{2}...\xi _{n}}
Oznake Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \xi _{i}} poprimaju sljedeće vrijednosti:
a) Ako znak Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle X_{i}} nije prazni znak, onda je oznaka Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \xi _{i}} jednaka $X_{i}$ .
b) Ako je znak $X_{i}$ prazni znak, onda je oznaka Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \xi _{i}} jednaka $\epsilon$ ili $X_{i}$ .
Produkcije se grade na temelju svih mogućih kombinacija oznaka Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \xi _{1}\xi _{2}...\xi _{n}} . Ako sve oznake $\xi _{i}$ poprime vrijednost $\epsilon$ , tada nastaje $\epsilon$ -produkcija i ona se ne dodaje u skup produkcija gramatike $G'$ . Time se odbace sve $\epsilon$ -produkcije iz zadane gramatike G.

Općenito će ovim algoritmom, ukoliko produkcija na desnoj strani ima k praznih znakova, biti potrebno izgraditi najviše Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{k}} novih produkcija. Ako je na desnoj strani barem jedan znak koji nije prazan, tada je potrebno dodati točno Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{k}} novih produkcija. Ako su na desnoj strani svi znakovi prazni, tada je potrebno dodati $2^{k}-1$ novih produkcija (produkcija Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\to \epsilon \epsilon ...\epsilon } se ne dodaje u skup produkcija).

Odbacivanje jediničnih produkcija

Neka gramatika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G=(V,T,P,S)} generira kontekstno neovisni jezik Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle L(G)\backslash \left\{\varepsilon \right\}} . Moguće je izgraditi istovjetnu gramatiku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle G'=(V',T',P',S)} koja nema jediničnih produkcija oblika $A\to B$ .

Istovjetna gramatika $G'$ koja nema jediničnih produkcija gradi se na sljedeći način:

U skup produkcija gramatike $G'$ stave se sve produkcije gramatike G koje nisu jedinične.
Neka se postupkom generiranja iz nezavršnog znaka A dobije nezavršni znak B, tj. $A\Rightarrow B$ , gdje su A i B nezavršni znakovi gramatike G. Za sve produkcije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle B\to \alpha } koje nisu jedinične grade se nove produkcije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle A\to \alpha } .