Chomsky Grammar

The mathematical definition of a language was developed by Noam Chomsky. 

The Chomsky hierarchy consists of the following levels: 

Type 0 – recursively enumerable languages 

Type 0 - recursive languages 

Type 1 – context-sensitive languages 

Type 2 – context-free languages 

Type 3 – regular languages

 1. A language L = L(T,N,P,S)is defined by: 

                    T- a dictionary of terminal symbols; 

                    N- a set of non-terminal symbols; 

                    P- a set of production rules (syntax rules); 

                    S- start symbol, which belongs to N. 

2. A language L(T,N,P,S)is a set of terminal symbol sequences ζ, which can be derived from S according to rule 3: 

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

T * letters denote symbol sequences from T 

3. A sequence δn can be derived from a sequence δ0 if and only if such sequences exist δ1, δ2,…., δn-1 such that each sequence δi can be directly derived from a sequence δi-1 according to rule 4.

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

4. A sequence η can be directly derived from a sequence ζ if and only if such sequences exist a, α, β, ζ’, η’ the following conditions are satisfied: 

a -> ζ = α ζ’ β 

b -> η = α η’ β 

c -> P consists production rule ζ’ ::= η’