Context-sensitive and Context-free Languages

Context-free language – a formal language, which is defined by the set of context-free rules. A production is context-free if and only if:

                                            
                                                
A ::= ξ (A ∈ N, ξ ∈(N ∪ T)*)

The left side of a context-free production consists of a single non-terminal symbol and can be replaced regardless of the context A appears in. If the production has the form of:

                                            
                                                
αAβ:: = αξβ

it is called a context-sensitive production, because a replacement by A can happen only in the context of α and β. 

Example 1: 

This example incorporates a grammar in which, by means of recursion, an infinite number of sentences can be generated by means of a finite set of productions. 


                                        
                                            
S ::= xA
A ::= z|yA

Set of sentences that can be generated from start symbol S:

                                
                                    
xz
xyz xyyz xyyyz ...