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]

  • 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]

poprawne reguły[edytuj]

(reguła z gramatyki lewostronnie regularnej)

reguły niepoprawne[edytuj]

(dwa symbole nieterminalne z lewej strony)
(dwa symbole nieterminalne z prawej strony)
(dwa symbole terminalne z prawej strony)

Przykład gramatyki[edytuj]

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]

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]

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 , i każdą regułę postaci:

Można przepisać do zestawu reguł:

Analogicznie przepisuje się reguły postaci:

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

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

  • Wybieramy jedną regułę postaci , której nie oznaczyliśmy jeszcze jako zbędnej
  • Dla każdej reguły postaci , dodajemy do zbioru reguł regułę postaci , 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 możemy teraz wyprowadzić samym . Jeśli natomiast wyprowadzenie słowa kończyło się , gdzie B było akceptujące, możemy to wyprowadzenie zakończyć na , które teraz również jest akceptujące.
  • Jeśli wszystkie reguły postaci są zaznaczone jako zbędne, usuwamy je i kończymy. Jeśli nie, wykonujemy kolejną iterację.

Zostają wtedy jedynie reguły postaci:

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

Łagodzenie zasad budowania reguł[edytuj]

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.:

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

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

Każdej gwiazdki pozbywa się wprowadzając nieterminalnych symbol pomocniczy , i dla regułki postaci tworzymy regułki:

Na przykład:

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 , , ... , pozostała tylko jedna regułka .
  • 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 i zamieniamy jego definicję na
    • 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

Na przykład weźmy gramatykę słów nad alfabetem nie zawierających podciągu . Gramatyka taka może mieć postać:

- jak dotąd nie wystąpiło
- jak dotąd nie wystąpiło, podejrzany prefiks to
- jak dotąd nie wystąpiło, podejrzany prefiks to
- jak dotąd nie wystąpiło, podejrzany prefiks to
- jak dotąd nie wystąpiło, podejrzany prefiks to
- jak dotąd nie wystąpiło
- jak dotąd nie wystąpiło, podejrzany prefiks to
- możemy skończyć jeśli nie ma podejrzanego prefiksu
- możemy skończyć jeśli podejrzany prefiks to
- możemy skończyć jeśli podejrzany prefiks to
- możemy skończyć jeśli podejrzany prefiks to

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

Łatwo można się pozbyć :

I :

musiby sprowadzić do wygodnej postaci:

I pozbyć się odniesienia do siebie samego:

Możemy teraz podstawić do :

Teraz już tylko grupujemy samo-odniesienia:

I usuwamy je:

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

Przypisy