Gramatyka Chomsky'ego

Matematyczna definicja języka została opracowana przez Noama Chomsky'ego. 

Hierarchia Chomsky`ego dzieli języki na cztery typy: 

Typ 0 – języki rekursywnie przeliczalne 

Typ 0 - języki rekursywne 

Typ 1 – języki kontekstowe 

Typ 2 – języki bezkontekstowe 

Typ 3- języki regularne

 1. Język L = L(T,N,P,S)jest definiowany przez: 

                    T- słownik symboli końcowych; 

                    N- zbiór symboli pomocniczych ( kategorii gramatycznych ); 

                    P- zbiór produkcji (reguł syntaktycznych ); 

                    S- symbol początkowy, należący do N, nazywany też głową języka. 

2. Język L(T,N,P,S) jest zbiorem ciągów symboli końcowych ζ, które mogą być wyprowadzone z S zgodnie z podaną poniżej regułą 3: 

L= {ζ | S→* ζ and ζ ∈ T*} 

T * oznacza zbiór wszystkich ciągów symboli z T 

3. Ciąg δn może być wyprowadzony z ciągu δ0 wtedy i tylko wtedy, gdy istnieją ciągi δ1, δ2,…., δn-1 takie, że każdy ciąg δi może być bezpośrednio wyprowadzony δi-1 zgodnie z podaną poniżej regułą 4.

                                            
                                                
(δ0→*δn) ↔ ((δi-1 → δi) for i = 1, … , n)

4. Ciąg η może być bezpośrednio wyprowadzony z ciągu ζ wtedy i tylko wtedy gdy istnieją ciągi α, β, ζ’, η’ takie, że:: 

a -> ζ = α ζ’ β 

b -> η = α η’ β 

c -> P zawiera produkcję ζ’ ::= η’