CONTEXT FREE GRAMMAR

About C.F.G. :- 

-> In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form

${\displaystyle A\ \to \ \alpha }$

with ${\displaystyle A}$ a single nonterminal symbol, and ${\displaystyle \alpha }$ a string of terminals and/or nonterminals (${\displaystyle \alpha }$ can be empty). A formal grammar is "context free" if its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar.

A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture,

${\displaystyle \langle {\text{Stmt}}\rangle \to \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}$

replaces ${\displaystyle \langle {\text{Stmt}}\rangle }$ with ${\displaystyle \langle {\text{Id}}\rangle =\langle {\text{Expr}}\rangle ;}$. There can be multiple replacement rules for a given nonterminal symbol. The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ("start symbol"). Nonterminal symbols are used during the derivation process, but do not appear in its final result string.

-> Languages generated by context-free grammars are known as context-free languages (CFL). Different context-free grammars can generate the same context-free language. It is important to distinguish the properties of the language (intrinsic properties) from the properties of a particular grammar (extrinsic properties). The language equality question (do two given context-free grammars generate the same language?) is undecidable.

-> Context-free grammars arise in linguistics where they are used to describe the structure of sentences and words in a natural language, and they were in fact invented by the linguist Noam Chomsky for this purpose.

-> Context-free grammar G can be defined by four tuples as:

G=(V,T,P,S)

Where,

G is the grammar, which consists of a set of the production rule. It is used to generate the string of a language.
T is the final set of a terminal symbol. It is denoted by lower case letters.

V is the final set of a non-terminal symbol. It is denoted by capital letters.

P is a set of production rules, which is used for replacing non-terminals symbols(on the left side of the production) in a string with other terminal or non-terminal symbols(on the right side of the production).
S is the start symbol which is used to derive the string. We can derive the string by repeatedly replacing a non-terminal by the right-hand side of the production until all non-terminal have been replaced by terminal symbols.

Example 1:
For the grammar given below, find out the context free language. The grammar G = ({S}, {a, b}, S, P) with the productions are;
S → aSa,           (Rule: 1)
S → bSb            (Rule: 2)
S →  ε               (Rule: 3)

Solution:

First compute some strings generated by  the production rules of the grammar G in the above;

(i)            S ⇒ aSa,                (Rule: 1)
⇒ aεa,               (Rule: 3) i.e.          ⇒ aa

(ii)           S ⇒ bSb,                (Rule: 2)

⇒ bεb,               (Rule: 3)

i.e.          ⇒ bb

(iii)          S ⇒ aSa,                (Rule: 1)
⇒ abSba,           (Rule: 2)
⇒ abεba            (Rule: 3)
i.e.          ⇒ abba

(iv)         S ⇒ bSb,                (Rule: 2)
⇒ baSab,           (Rule: 1)
⇒ ba ε ab         (Rule: 3)
i.e.          ⇒ baab

(v)          S ⇒ aSa,                (Rule: 1)
⇒ aaSaa,           (Rule: 1)
⇒ aabSbaa,      (Rule: 2)
⇒ aabbSbbaa, (Rule: 2)
⇒ aabb ε bbaa (Rule: 3)
i.e.          ⇒ aabbbbaa

Hence; Language generated by the above grammar L(G) = {aa, bb, abba, baab, aabbaa, aabbbbaa,.. .. .. .. }

By analyzing the above generated string form the grammar G, there has a similar pattern in all computed strings, i.e.

• The length of the string is even always i.e. length of the string L(w) ≥ 2 × i | i = 1, 2, 3, 4.. .
• From the half length of the string, string is the reverser of each other side i.e. string is generated by the language is palindrome.

Thus we can write the language of the grammar L(G) = {wwR : w ∈ {a, b}*};