Gramatyka formalna: Różnice pomiędzy wersjami

Z Wikipedii, wolnej encyklopedii
[wersja nieprzejrzana][wersja nieprzejrzana]
Usunięta treść Dodana treść
DodekBot (dyskusja | edycje)
Nie podano opisu zmian
Linia 1: Linia 1:
'''Gramatyką formalną''' nazywamy sposób opisu [[język formalny|języka formalnego]], czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.
'''Gramatyką formalną''' nazywamy sposób opisu [[język formalny|języka formalnego]], czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.


Aby zdefiniować gramatykę formalną trzeba określić zbiór '''symboli terminalnych''', zbiór '''symboli nieterminalnych''', '''[[symbol startowy]]''', oraz zbiór '''reguł''' które określają sposób w jaki wyprowadzamy słowa.
Aby zdefiniować gramatykę formalną trzeba określić zbiór '''[[symbol terminalny|symboli terminalnych]]''', zbiór '''[[symbol nieterminalny|symboli nieterminalnych]]''', '''[[symbol startowy]]''', oraz zbiór '''reguł''' które określają sposób w jaki wyprowadzamy słowa.


Symbole terminalne (równoważne symbolom alfabetu języka) są symbolami, które pozostaną w wyprowadzonym słowie &ndash; w przeciwieństwie do symboli nieterminalnych używanych tylko podczas wyprowadzania słowa. Reguły gramatyki postaci <math>S_1 \rightarrow S_2</math>, gdzie <math>S_1</math> i <math>S_2</math> to ciągi symboli terminalnych i nieterminalnych, określają możliwe podstawienia symboli w wyprowadzanym słowie. Wyprowadzanie rozpoczynamy od ciągu złożonego z wyróżnionego symbolu nazywanego symbolem początkowym. Odbywa się ono przez zastępowanie podciągów tego ciągu zgodnie z regułami gramatyki. Jeśli w ciągu mamy podciąg <math>S_1</math>, możemy zastąpić go przez <math>S_2</math>.
Symbole terminalne (równoważne symbolom alfabetu języka) są symbolami, które pozostaną w wyprowadzonym słowie &ndash; w przeciwieństwie do symboli nieterminalnych używanych tylko podczas wyprowadzania słowa. Reguły gramatyki postaci <math>S_1 \rightarrow S_2</math>, gdzie <math>S_1</math> i <math>S_2</math> to ciągi symboli terminalnych i nieterminalnych, określają możliwe podstawienia symboli w wyprowadzanym słowie. Wyprowadzanie rozpoczynamy od ciągu złożonego z wyróżnionego symbolu nazywanego symbolem początkowym. Odbywa się ono przez zastępowanie podciągów tego ciągu zgodnie z regułami gramatyki. Jeśli w ciągu mamy podciąg <math>S_1</math>, możemy zastąpić go przez <math>S_2</math>.

Wersja z 22:40, 20 sty 2007

Gramatyką formalną nazywamy sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.

Aby zdefiniować gramatykę formalną trzeba określić zbiór symboli terminalnych, zbiór symboli nieterminalnych, symbol startowy, oraz zbiór reguł które określają sposób w jaki wyprowadzamy słowa.

Symbole terminalne (równoważne symbolom alfabetu języka) są symbolami, które pozostaną w wyprowadzonym słowie – w przeciwieństwie do symboli nieterminalnych używanych tylko podczas wyprowadzania słowa. Reguły gramatyki postaci , gdzie i to ciągi symboli terminalnych i nieterminalnych, określają możliwe podstawienia symboli w wyprowadzanym słowie. Wyprowadzanie rozpoczynamy od ciągu złożonego z wyróżnionego symbolu nazywanego symbolem początkowym. Odbywa się ono przez zastępowanie podciągów tego ciągu zgodnie z regułami gramatyki. Jeśli w ciągu mamy podciąg , możemy zastąpić go przez .

Rozważmy przykładową gramatykę z symbolem nieterminalnym S, który jest jednocześnie symbolem startowym, oraz zbiorem symboli terminalnych . Reguły tej gramatyki, która umożliwia generowanie słów postaci ba, abab, aababb, aaababbb itd. wyglądają następująco:

Zaczynamy od symbolu startowego S, możemy zastąpić go przez aSb zgodnie z pierwszą regułą. Możemy użyć jej jeszcze raz otrzymując aaSbb. Po użyciu drugiej reguły pozostanie nam ciąg aababb. Składa się on tylko z symboli terminalnych, więc wyprowadzenie słowa zostało zakończone.

Symbol startowy

Wymaganie, żeby symbol startowy był jeden, nie ogranicza nam szczególnie możliwości budowania gramatyk.

Jeśli chcemy zacząć generację od jakiegoś innego słowa , lub od pewnych kilku możliwych słów , możemy dodać symbol "przedstartowy" , oraz regułki postaci , o ile takie regułki mieszczą się w podzbiorze dozwolonych regułek dla danego typu gramatyk.

Wystarcza nam więc jeden symbol startowy, niezależnie od tego, od ilu możliwych słów zamierzamy zaczynać.

Symbole terminalne i nieterminalne

Nie ogranicza nas też specjalnie podział na symbole terminalne i nieterminalne. Jeśli chcemy możemy nawet wymagać, żeby po lewej stronie każdej regułki były tylko symbole nieterminalne.

Jeśli mamy w którymś miejscu symbol terminalny , a chcemy mieć tam symbol nieterminalny, to tworzymy specjalny symbol nieterminalny , i regułkę . Wtedy wszędzie oprócz tej regułki zamiast używamy .

Dla przykładu, załóżmy że mamy gramatykę:

I chcemy żeby po lewej stronie były tylko symbole nieterminalne. Dodajemy więc regułki:

A te już istniejące zamieniamy na:

Tej techniki używa się np. w budowaniu postaci normalnej Chomsky'ego gramatyk bezkontekstowych.

Alternatywa języków

Załóżmy że mamy gramatyki generującą język i , generującą język , i chcemy uzyskać język wszystkich słów które są albo w albo w .

W tym celu tworzymy symbol startowy i dodajemy regułki przepisania go na symbol startowy pierwszego bądź drugiego języka:

oraz wszystkie regułki obu gramatyk.

Słowo będzie więc należało do języka jeśli da się wyprowadzić w jednej z gramatyk. Musimy jednak zadbać o to, żeby nie wolno było mieszać wyprowadzeń – tak, że część słowa jest wyprowadzona pierwszą gramatyką, a część drugą. Zanim więc połączymy zbiory reguł obu gramatyk, przekształćmy je najpierw tak, żeby po lewej stronie wszystkich reguł były wyłącznie nieterminale, i zmieńmy nazwy wszystkich nieterminali, żeby żaden nieterminal nie występował jednocześnie w obu gramatykach (to jak nazwane będą nieterminale nie wpływa w żaden sposób na to, jaki język dana gramatyka generuje). Jeśli gramatyki są tej postaci, to w żaden sposób nie da się w jednym wyprowadzeniu użyć reguł obu gramatyk.

Algorytm taki nie istnieje dla dopełnienia języka (zbioru wszystkich słów które nie należą do danego języka). Jest nawet możliwe, że dany język opisuje jakaś gramatyka, ale dla zbioru słów nie należących do niego nie ma żadnej gramatyki).

Dla dwóch gramatyk potrafimy też znaleźć gramatykę przecięcia języków (zbioru słów należących do obu języków), ale jej postać może być o wiele trudniejsza od postaci gramatyk oryginalnych.

Klasy gramatyk

Ograniczając postać reguł wyprowadzania otrzymujemy klasy gramatyk, takie jak (szczegółowo w artykule hierarchia Chomsky'ego):

Gramatyka regularna (odpowiednio: bezkontekstowa, kontekstowa) zawsze generuje język regularny (odp.: bezkontekstowy, kontekstowy). Jednak możliwe jest też, że pewna gramatyka, która nie jest regularna (bezkontekstowa, kontekstowa), generuje język regularny (bezkontekstowy, kontekstowy). W takim przypadku zawsze istnieje też gramatyka o regułach prostszej postaci generująca ten sam język.