Gramatyka formalna: Różnice pomiędzy wersjami

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>.

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.

[[Kategoria:językiJęzyki formalne]]