Gramatyka formalna
Gramatyka formalna – sposób opisu języka formalnego, czyli podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem.

Do zdefiniowania gramatyki formalnej potrzebne jest określenie zbioru symboli terminalnych, zbioru symboli nieterminalnych, symbolu startowego oraz zbioru reguł określających sposób wyprowadzania słów.

Symbol nieterminalny to symbol, który można definiować. Symbole nieterminalne zwane są również zmiennymi syntaktycznymi, ponieważ umożliwiają tworzenie ciągów zawierających kombinacje symboli terminalnych i nieterminalnych.

Symbol terminalny to symbol elementarny tworzący wyrazy języka formalnego. Symbole terminalne są znakami, które mogą pojawić się na wejściu lub wyjściu z reguł produkcji gramatyki formalnej. Symbol terminalny nie może być podzielony na „mniejsze” jednostki, lub ściślej: symbole terminalne nie mogą być zmieniane za pomocą reguł gramatyki formalnej, w odróżnieniu od symboli nieterminalnych.

Gramatyka formalna posiada wyróżniony symbol nieterminalny, zwany symbolem startowym, od którego, poprzez stosowanie reguł produkcji, zaczyna się wyprowadzanie wszystkich wyrazów języka formalnego. Tworzenie wyrazu języka formalnego kończy się wówczas gdy zawiera on już tylko symbole terminalne.

Symbole terminalne (równoważne symbolom alfabetu języka) są symbolami, które pozostaną w wyprowadzonym słowie – w przeciwieństwie do symboli nieterminalnych używanych tylko podczas wyprowadzania słowa. Reguły gramatyki postaci formula_1 gdzie formula_2 i formula_3 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 formula_4 możemy zastąpić go przez formula_5

Rozważmy przykładową gramatykę z symbolem nieterminalnym S, który jest jednocześnie symbolem startowym, oraz zbiorem symboli terminalnych formula_6
Reguły tej gramatyki, która umożliwia generowanie słów postaci ba, abab, aababb, aaababbb itd. wyglądają następująco:
* formula_7
* formula_8

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.
Q192161
języka formalnego
Concept
Q192161
języka formalnego
Concept
Q9348872
symbolem startowym
UNK
Q373045
Gramatyka formalna
Concept
Q373045
Gramatyka formalna
Concept
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
+2^^http://www.w3.org/2001/XMLSchema#decimal
2
NUMBER
+3^^http://www.w3.org/2001/XMLSchema#decimal
3
NUMBER
+4^^http://www.w3.org/2001/XMLSchema#decimal
4
NUMBER
+5^^http://www.w3.org/2001/XMLSchema#decimal
5
NUMBER
+6^^http://www.w3.org/2001/XMLSchema#decimal
6
NUMBER
+7^^http://www.w3.org/2001/XMLSchema#decimal
7
NUMBER
+8^^http://www.w3.org/2001/XMLSchema#decimal
8
NUMBER
part of
part of
has quality