Gramatyka regularna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Gramatyka regularna to 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ł[edytuj | edytuj kod]

  • 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. [1]

Przykłady[edytuj | edytuj kod]

poprawne reguły[edytuj | edytuj kod]

A \rightarrow A
A \rightarrow B
A \rightarrow aA
A \rightarrow aB
A \rightarrow \epsilon
A \rightarrow a
A \rightarrow Ca (reguła z gramatyki lewostronnie regularnej)

reguły niepoprawne[edytuj | edytuj kod]

AB \rightarrow cD (dwa symbole nieterminalne z lewej strony)
A \rightarrow BC (dwa symbole nieterminalne z prawej strony)
A \rightarrow Baa (dwa symbole terminalne z prawej strony)

Przykład gramatyki[edytuj | edytuj kod]

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 gdzie zbór reguł N = {S,A,B,C,D,E,F} oraz alfabet Σ = {0,1,2,3,4,5,6,7,8,9,+,-,.,e}, symbol S będzie symbolem startowym, ε będzie pustym ciągiem.

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[edytuj | edytuj kod]

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ł[edytuj | edytuj kod]

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_2 \rightarrow c_3P_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.

Łagodzenie zasad budowania reguł[edytuj | edytuj kod]

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}

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\rightarrow aS - jak dotąd baba nie wystąpiło
S\rightarrow bP_{b} - jak dotąd baba nie wystąpiło, podejrzany prefiks to b
P_b\rightarrow bP_b - jak dotąd baba nie wystąpiło, podejrzany prefiks to b
P_b\rightarrow aP_{ba} - jak dotąd baba nie wystąpiło, podejrzany prefiks to ba
P_{ba}\rightarrow bP_{bab} - jak dotąd baba nie wystąpiło, podejrzany prefiks to bab
P_{ba}\rightarrow aS - jak dotąd baba nie wystąpiło
P_{bab}\rightarrow bP_b - jak dotąd baba nie wystąpiło, podejrzany prefiks to b
S\rightarrow \epsilon - możemy skończyć jeśli nie ma podejrzanego prefiksu
P_b\rightarrow \epsilon - możemy skończyć jeśli podejrzany prefiks to b
P_{ba}\rightarrow \epsilon - możemy skończyć jeśli podejrzany prefiks to ba
P_{bab}\rightarrow \epsilon - możemy skończyć jeśli podejrzany prefiks to bab

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

S\rightarrow aS | bP_{b} | \epsilon
P_b\rightarrow bP_b | aP_{ba} | \epsilon
P_{ba}\rightarrow bP_{bab} | aS | \epsilon
P_{bab}\rightarrow bP_b | \epsilon

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

S\rightarrow aS | bP_{b} | \epsilon
P_b\rightarrow bP_b | aP_{ba} | \epsilon
P_{ba}\rightarrow b(bP_b | \epsilon) | aS | \epsilon

I P_{ba}:

S\rightarrow aS | bP_{b} | \epsilon
P_b\rightarrow bP_b | a(b(bP_b | \epsilon) | aS | \epsilon) | \epsilon

P_b musiby sprowadzić do wygodnej postaci:

P_b\rightarrow ((b|abb)P_b) | (ab | aaS | a | \epsilon)

I pozbyć się odniesienia do siebie samego:

P_b\rightarrow (b|abb)^*(ab | aaS | a | \epsilon)

Możemy teraz podstawić do S:

S\rightarrow aS | b(b|abb)^*(ab | aaS | a | \epsilon) | \epsilon

Teraz już tylko grupujemy samo-odniesienia:

S\rightarrow (a | b(b|abb)^*aa)S | (b(b|abb)^*(ab | a | \epsilon) | \epsilon)

I usuwamy je:

S\rightarrow (a | b(b|abb)^*aa)^* (b(b|abb)^*(ab | a | \epsilon) | \epsilon)

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

Przypisy