Gramatyka formalna: Różnice pomiędzy wersjami

Dodane 47 bajtów ,  14 lat temu
brak opisu edycji
'''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 '''[[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>.
Anonimowy użytkownik