Gramatyka formalna: Różnice pomiędzy wersjami

Usunięte 8 bajtów ,  10 lat temu
m
WPCleaner 0.99 - Kategorie zaczynające się małą literą - Sekwencje specjalne HTML: en/em dash (WP:CHECK)
m (robot dodaje: sk:Gramatika (informatika))
m (WPCleaner 0.99 - Kategorie zaczynające się małą literą - Sekwencje specjalne HTML: en/em dash (WP:CHECK))
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>.
 
Rozważmy przykładową gramatykę z symbolem nieterminalnym S, który jest jednocześnie symbolem startowym, oraz zbiorem symboli terminalnych <math>\{a,b\}</math>.
: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ń''' &ndash; 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).
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.
 
[[Kategoria:językiJęzyki formalne]]
[[Kategoria:Gramatyka]]
 
5755

edycji