Gramatyka regularna

Z Wikipedii

Gramatyka regularna to gramatyka formalna generująca język regularny.

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 tylko na końcu prawej strony. Symbole terminalne mogą występować tylko na początku lewej strony.

Przykłady poprawnych reguł:

$A \rightarrow A$

$A \rightarrow B$

$A \rightarrow aA$

$A \rightarrow aB$

$A \rightarrow abcA$

$A \rightarrow abcB$

$A \rightarrow \epsilon$

$A \rightarrow a$

$A \rightarrow abc$

Przykłady reguł niepoprawnych:

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

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

$A \rightarrow Ba$ (symbol nieterminalny nie znajduje się na końcu prawej strony)

[edytuj] 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 \rightarrow c_1c_2c_3\cdots c_kB$

Można przepisać do zestawu reguł:

$A \rightarrow c_1P_1$

$P_1 \rightarrow c_2P_2$

$P_3 \rightarrow c_2P_3$

$\vdots$

$P_{k-1} \rightarrow c_kB$

Analogicznie przepisuje się reguły postaci:

$A \rightarrow c_1c_2c_3\cdots c_k$

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

$A \rightarrow B$

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

Wybieramy jedną regułę postaci $A \rightarrow B$ , której nie oznaczyliśmy jeszcze jako zbędnej
Dla każdej reguły postaci $B \rightarrow \Gamma$ , dodajemy do zbioru reguł regułę postaci $A \rightarrow \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\rightarrow B\rightarrow \Gamma$ możemy teraz wyprowadzić samym $A\rightarrow\Gamma$ . Jeśli natomiast wyprowadzenie słowa kończyło się $A\rightarrow 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 \rightarrow B$ są zaznaczone jako zbędne, usuwamy je i kończymy. Jeśli nie, wykonujemy kolejną iterację.

Zostają wtedy jedynie reguły postaci:

$A\rightarrow a$

$A\rightarrow aB$

$A\rightarrow \epsilon$

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

[edytuj] Ł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\rightarrow 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\rightarrow aB$

$A\rightarrow aaa(C|bD)$

$A\rightarrow aaaC$

$A\rightarrow 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\rightarrow aa(ab)^*bb(a)^*B$

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

$A \rightarrow \alpha P$

$P \rightarrow \beta P$

$P \rightarrow \gamma$

Na przykład:

$A\rightarrow aa(ab)^*bb(a)^*B$

$A\rightarrow aaP_1$

$P_1 \rightarrow ab P_1$

$P_1 \rightarrow bbP_2$

$P_2 \rightarrow aP_2$

$P_2 \rightarrow 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\rightarrow \Gamma_1$ , $A\rightarrow \Gamma_2$ , ... , $A\rightarrow \Gamma_k$ pozostała tylko jedna regułka $A \rightarrow \Gamma_1 | \Gamma_2 | \cdots | \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 \rightarrow ((\Gamma_1 | \cdots | \Gamma_k) A) | (\Gamma_{k+1} | \cdots | \Gamma_n)$ i zamieniamy jego definicję na $A \rightarrow (\Gamma_1 | \cdots | \Gamma_k)^* (\Gamma_{k+1} | \cdots | \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 \rightarrow \mbox{wyrażenie regularne}$