Gramatyka formalna: Różnice pomiędzy wersjami

Dodane 28 bajtów ,  7 lat temu
m
WP:SK, drobne techniczne {{subst:źd}}
(lit.)
m (WP:SK, drobne techniczne {{subst:źd}})
{{Źródła|data=2013-09 }}
'''Gramatyka formalna''' – sposób opisu [[język formalny|języka formalnego]], czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.
 
 
== Symbol startowy ==
 
Wymaganie, żeby symbol startowy był jeden, nie ogranicza nam szczególnie możliwości budowania gramatyk.
 
 
== 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ły były '''tylko symbole nieterminalne'''.
 
== Alternatywa języków ==
 
Załóżmy że mamy gramatykę <math>G_1</math> generującą język <math>L_1</math> i <math>G_2</math>, generującą język <math>L_2</math>; chcemy uzyskać język wszystkich słów które są albo w <math>L_1</math> albo w <math>L_2</math>.
 
W tym celu tworzymy symbol startowy <math>S</math> i dodajemy regułki przepisania go na symbol startowy pierwszego bądź drugiego języka:
: <math>S\rightarrow S_1</math>
: <math>S\rightarrow S_2</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ń''' – 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.
 
== Klasy gramatyk ==
 
'''Ograniczając postać reguł''' wyprowadzania, otrzymujemy klasy gramatyk, takie jak (szczegółowo w artykule [[hierarchia Chomsky'ego]]):
* [[gramatyka regularna|gramatyki regularne]]
95 889

edycji