Gramatyka regularna

Gramatyka regularna – gramatyka formalna, za pomocą której można opisać język regularny.

Istnieją dwa rodzaje gramatyk regularnych: gramatyka lewostronna, gramatyka prawostronna. Istnieje ścisły związek gramatyki lewostronnej oraz deterministycznego automatu skończonego, taki że gramatyka generuje dokładnie taki język, jaki akceptuje automat. Stąd gramatyki lewostronne generują dokładnie wszystkie języki regularne.

Gramatyka regularna to albo prawo- albo lewostronna.

Ważne ograniczenia postaci reguł

• Po lewej stronie występuje zawsze dokładnie jeden symbol nieterminalny (tak samo jak w gramatykach bezkontekstowych)
• Po prawej stronie występuje nie więcej niż jeden symbol nieterminalny i dowolny łańcuch symboli terminalnych. W gramatykach prawostronnie regularnych symbol terminalny występuje przed nieterminalnym (jeśli ten się tam znajduje), a w lewostronnie regularnych na odwrót.

Przykłady

poprawne reguły

$A\to A$

$A\to B$

$A\to aA$

$A\to aB$

$A\to ϵ$

$A\to a$

$A\to Ca$ (reguła z gramatyki lewostronnie regularnej)

reguły niepoprawne

$AB\to cD$ (dwa symbole nieterminalne z lewej strony)

$A\to BC$ (dwa symbole nieterminalne z prawej strony)

Przykład gramatyki

Jako przykład z zakresu języków programowania może posłużyć gramatyka opisująca ciągi znaków będące zapisem liczb zmiennoprzecinkowych. Poniżej przedstawiono gramatykę G ze zbiorem reguł N = {S,A,B,C,D,E,F} i alfabetem Σ = {0,1,2,3,4,5,6,7,8,9,+,-,.,e}. Symbol S jest symbolem startowym, zaś przez ε oznaczamy ciąg pusty.

S → +A	A → 0A	B → 0C	C → 0C	D → +E	E → 0F	F → 0F
S → -A	A → 1A	B → 1C	C → 1C	D → -E	E → 1F	F → 1F
S → A	A → 2A	B → 2C	C → 2C	D → E	E → 2F	F → 2F
	A → 3A	B → 3C	C → 3C		E → 3F	F → 3F
	A → 4A	B → 4C	C → 4C		E → 4F	F → 4F
	A → 5A	B → 5C	C → 5C		E → 5F	F → 5F
	A → 6A	B → 6C	C → 6C		E → 6F	F → 6F
	A → 7A	B → 7C	C → 7C		E → 7F	F → 7F
	A → 8A	B → 8C	C → 8C		E → 8F	F → 8F
	A → 9A	B → 9C	C → 9C		E → 9F	F → 9F
	A →.B		C → eD			F → ε
	A → B		C → ε

Łączenie gramatyk

Za pomocą łączenia prawo i lewostronnych gramatyk można tworzyć języki, które niekoniecznie będą regularne, z definicji jednak, tego typu gramatyki nie będą już regularne.

Zaostrzanie zasad tworzenia reguł

Reguły te można zaostrzyć bez straty mocy, pozwalając na co najwyżej jeden symbol terminalny z prawej strony. Wprowadza się w tym celu kilka stanów pomocniczych $P_i,$ i każdą regułę postaci:

$A\to c_1{c}_2{c}_3\cdots c_{k}B$

Można przepisać do zestawu reguł:

$A\to c_1{P}_1$

$P_1\to c_2{P}_2$

$P_2\to c_3{P}_3$

$⋮$

$P_{k-1}\to c_{k}B$

Analogicznie przepisuje się reguły postaci:

$A\to c_1{c}_2{c}_3\cdots c_k$

Drugim często nakładanym ograniczeniem jest zabranianie reguł, które zmieniają stan bez czytania żadnych symboli:

$A\to B$

Algorytm pozbywania się ich jest następujący:

• Wybieramy jedną regułę postaci $A\to B,$ której nie oznaczyliśmy jeszcze jako zbędnej
• Dla każdej reguły postaci $B\to \mathrm{\Gamma },$ dodajemy do zbioru reguł regułę postaci $A\to \mathrm{\Gamma },$ chyba że taka już istnieje
• Jeśli B było akceptujące, A natomiast nie było, zaznaczamy A jako akceptujące
• Zaznaczamy wybraną regułę jako zbędną – każde słowo, w którego wyprowadzeniu były użyte reguły $A\to B\to \mathrm{\Gamma }$, możemy teraz wyprowadzić samym $A\to \mathrm{\Gamma }.$ Jeśli natomiast wyprowadzenie słowa kończyło się $A\to B,$ gdzie B było akceptujące, możemy to wyprowadzenie zakończyć na $A,$ które teraz również jest akceptujące.
• Jeśli wszystkie reguły postaci $A\to B$ są zaznaczone jako zbędne, usuwamy je i kończymy. Jeśli nie, wykonujemy kolejną iterację.

Zostają wtedy jedynie reguły postaci:

$A\to a$

$A\to aB$

$A\to ϵ$

Z takich reguł bardzo łatwo już przejść do niedeterministycznego automatu skończonego.

Łagodzenie zasad budowania reguł

Można też pozwolić na łagodniejsze reguły – kierując się w stronę wyrażeń regularnych. Bez zmiany mocy gramatyk regularnych wolno dodać alternatywę, przy czym na symbole nieterminalne po prawej stronie nakłada się ograniczenie, że muszą one się znajdować na końcu dowolnej ścieżki wyboru alternatyw, np.:

$A\to a(B|aa(C|bD))$

Przejście do tradycyjnych gramatyk regularnych dokonuje się, rozbijając każdą alternatywę na parę regułek, aż pozbędziemy się ostatniej:

$A\to aB$

$A\to aaa(C|bD)$

$A\to aaaC$

$A\to aaabD$

Można też dodać gwiazdkę, oznaczającą powtórzenie fragmentu dowolnie wiele razy, o ile wewnątrz niej znajdują się tylko symbole terminalne, np.:

$A\to aa(ab{)}^{*}bb(a{)}^{*}B$

Każdej gwiazdki pozbywa się, wprowadzając nieterminalnych symbol pomocniczy $P,$ i dla regułki postaci $A\to \alpha {\beta }^{*}\gamma$ tworzymy regułki:

$A\to \alpha P$

$P\to \beta P$

$P\to \gamma$

Na przykład:

$A\to aa(ab{)}^{*}bb(a{)}^{*}B$

$A\to aa{P}_1$

$P_1\to ab{P}_1$

$P_1\to bb{P}_2$

$P_2\to a{P}_2$

$P_2\to B$

Używając (z podanymi wyżej ograniczeniami) gwiazdki i alternatywy, możemy mieszać gramatyki regularne i wyrażenia regularne. Można też dla każdej gramatyki regularnej zbudować odpowiadające jej wyrażenie regularne. Konstrukcja jest następująca:

• Przepisujemy gramatykę z użyciem alternatywy, tak żeby dla każdego symbolu nieterminalnego o regułkach $A\to {\mathrm{\Gamma }}_1,$ $A\to {\mathrm{\Gamma }}_2,...,$ $A\to {\mathrm{\Gamma }}_k$ pozostała tylko jedna regułka $A\to {\mathrm{\Gamma }}_1|{\mathrm{\Gamma }}_2|\cdots |{\mathrm{\Gamma }}_k.$
• Wybieramy jeden symbol nieterminalny, oprócz symbolu startowego:
  • Jeśli w jego definicji znajduje się odwołanie do niego samego, przestawiamy te alternatywy do postaci $A\to (({\mathrm{\Gamma }}_1|\cdots |{\mathrm{\Gamma }}_k)A)|({\mathrm{\Gamma }}_{k+1}|\cdots |{\mathrm{\Gamma }}_n)$ i zamieniamy jego definicję na $A\to ({\mathrm{\Gamma }}_1|\cdots |{\mathrm{\Gamma }}_k{)}^{*}({\mathrm{\Gamma }}_{k+1}|\cdots |{\mathrm{\Gamma }}_n)$
  • Skoro w definicji A nie ma już żadnych odwołań do samego siebie, podstawiamy definicję A w miejsce wszystkich wystąpień A w innych regułkach. Otrzymujemy w ten sposób układ zawierający o jeden symbol mniej.
• Na końcu zostaje nam tylko symbol startowy. Jeśli zawiera odwołanie do samego siebie, musimy go przekształcić zgodnie z tą samą procedurą.
• Gramatyka jest postaci $S\to \text{wyrażenie regularne}$

Na przykład weźmy gramatykę słów nad alfabetem $\{a,b\}$ nie zawierających podciągu $baba.$ Gramatyka taka może mieć postać:

$S\to aS$ – jak dotąd $baba$ nie wystąpiło

$S\to b{P}_b$ – jak dotąd $baba$ nie wystąpiło, podejrzany prefiks to $b$

$P_b\to b{P}_b$ – jak dotąd $baba$ nie wystąpiło, podejrzany prefiks to $b$

$P_b\to a{P}_{ba}$ – jak dotąd $baba$ nie wystąpiło, podejrzany prefiks to $ba$

$P_{ba}\to b{P}_{bab}$ – jak dotąd $baba$ nie wystąpiło, podejrzany prefiks to $bab$

$P_{ba}\to aS$ – jak dotąd $baba$ nie wystąpiło

$P_{bab}\to b{P}_b$ – jak dotąd $baba$ nie wystąpiło, podejrzany prefiks to $b$

$S\to ϵ$ – możemy skończyć, jeśli nie ma podejrzanego prefiksu

$P_b\to ϵ$ – możemy skończyć, jeśli podejrzany prefiks to $b$

$P_{ba}\to ϵ$ – możemy skończyć, jeśli podejrzany prefiks to $ba$

$P_{bab}\to ϵ$ – możemy skończyć, jeśli podejrzany prefiks to $bab$

Można ją przepisać do układu równań gramatycznych:

$S\to aS|b{P}_b|ϵ$

$P_b\to b{P}_b|a{P}_{ba}|ϵ$

$P_{ba}\to b{P}_{bab}|aS|ϵ$

$P_{bab}\to b{P}_b|ϵ$

Łatwo można się pozbyć $P_{bab}:$

$S\to aS|b{P}_b|ϵ$

$P_b\to b{P}_b|a{P}_{ba}|ϵ$

$P_{ba}\to b(b{P}_b|ϵ)|aS|ϵ$

I $P_{ba}:$

$S\to aS|b{P}_b|ϵ$

$P_b\to b{P}_b|a(b(b{P}_b|ϵ)|aS|ϵ)|ϵ$

$P_b$ musiby sprowadzić do wygodnej postaci:

$P_b\to ((b|abb)P_b)|(ab|aaS|a|ϵ)$

I pozbyć się odniesienia do siebie samego:

$P_b\to (b|abb{)}^{*}(ab|aaS|a|ϵ)$

Możemy teraz podstawić do $S:$

$S\to aS|b(b|abb{)}^{*}(ab|aaS|a|ϵ)|ϵ$

Teraz już tylko grupujemy samo-odniesienia:

$S\to (a|b(b|abb{)}^{*}aa)S|(b(b|abb{)}^{*}(ab|a|ϵ)|ϵ)$

I usuwamy je:

$S\to (a|b(b|abb{)}^{*}aa{)}^{*}(b(b|abb{)}^{*}(ab|a|ϵ)|ϵ)$

W ten sposób mechanicznie stworzyliśmy wyrażenie regularne, którego ręczne zbudowanie byłoby znacznie trudniejsze.