Gramatyka formalna: Różnice pomiędzy wersjami

Dodane 8 bajtów ,  15 lat temu
drobne
m (robot dodaje: pt:Gramática formal)
(drobne)
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.
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.
Tej techniki używa się np. w budowaniu [[postać normalna Chomsky'ego|postaci normalnej Chomsky'ego]] [[gramatyka bezkontekstowa|gramatyk bezkontekstowych]].
 
== Alternatywa języków ==
 
Załóżmy że mamy gramatyki <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>, i chcemy uzyskać język wszystkich słów które są albo w <math>L_1</math> albo w <math>L_2</math>.
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]]):
Anonimowy użytkownik