Gramatyka formalna –podzbioru zbioru wszystkich słów skończonej długości nad danym alfabetem. Aby zdefiniować gramatykę formalną trzeba określić zbiór symboli terminalnych, zbiór symboli nieterminalnych, symbol startowy, oraz zbiór reguł które określają sposób w jaki wyprowadzamy słowa. 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...