Context Free Grammars (CFG) | Theory of Computation - Computer Science Engineering (CSE) PDF Download

Context Free Grammars and Languages

• As we learned in the first module, according to Chomsky classification, Type- 2 languages are also called context-free languages. 
• They are generated using context-free grammars. They are recognized using push-down automata.
  Also, regular languages are a subset of context-free languages.
  

Part I. Context Free Grammars (CFG)

G = (V,∑, P, S)

where

V is a set of non-terminals,

∑ is a set of terminals,

S is the start symbol,

P is a set of productions.

A grammar, G is context free, if productions are of the form, α → β
where α is a single non terminal.

Every regular grammar is context free.

Example 1: An example for context free grammar is shown below:
S → ASA|BSB|a|b
A → a
B → b
where S is the start symbol.

From the definition of CFG,
G = {S, A, B}
P = {a, b}
P = {S → ASA|BSB|a|b, A → a, B → b}
S = S

The production,
S → ASA|BSB|a|b
can also be written as,
S → ASA
S → BSB
S → a
S → b

Example 2: The following is an example for context free grammar.
Stmt → id = Expr;
Stmt → if (Expr) Stmt
Stmt → if (Expr) Stmt else Stmt
Stmt → while (Expr) Stmt
Stmt → do Stmt while (Expr);
Stmt→ { Stmts }

Stmts → Stmts Stmt| ε
where Stmts is the start symbol.

From the definition of CFG,
G = {Stmts, stmt, Expr}
∑ = {id, =, ; ,(,), if, else, while, do}
P is the set of productions given above
S = Stmts

Note that above CFG corresponds to some statements in C programming language.

Language of Context Free Grammar (Context Free Language)

Example 1: Consider the following context free grammar.
S → aA|bB
A → x
B → y
The language corresponding to the above CFG is {ax,by}

A string w belongs to a context free language (CFL), L, if it can be derived from the CFG associated with L.
That is,

There are two approaches to check whether a string belongs to a CFL. They are, Derivations, and Reductions.

Derivations

Example 1: Consider the following CFG.

S → aSb | ab

where S is the start symbol.

Check whether the string aabb belongs to the CFL corresponding to above CFG.

Above diagram is called a derivation tree (parse tree).

Here, by performing two derivations, we got a2b2. So a2b2 belongs to the above CFL.

Example 2: Consider the following CFG.
S → aSa | bSb |c
where S is the start symbol.
Check whether the string abbcbba belongs to the language corresponding to the above grammar.

From the above derivation tree, the string abbcbba is derived using the given CFG. So the string abbcbba belongs to the above language.

Example 3: Consider the CFG.
S → aAS|a|SS
A → SbA|ba
where S is the start symbol.
Check whether the string aabaa can be derived using the above grammar.


Example 4: Consider the CFG.
S → aAS|a
A → SbA|SS|ba
where S is the start symbol.
Check whether the string aabbaa belongs to this language.
Following is the derivation tree:

Thus the above string aabbaa or a²b²a² belongs to the above CFL.

Reductions

Example 1: Consider the grammar.
S → aAS|a|SS
A → SbA|ba
where S is the start symbol.
Check whether the string aabaa belongs to the CFL associated with the above grammar.
The reduction tree is shown below:

Thus by performing a number of reductions, we finally reached the start symbol. So the string aabaa belongs to the above CFL.

2 CFG corresponding to a CFL

L = {anbn| n ≥ 0}

At n=0, ε is a valid string for the above language. The production for this is,

S → ε

Every string is of length 2n. The strings are ab, abab, aaabbb, ......... etc..

The corresponding production is,

S → aSb.

Hence the grammar is,

S → aSb | ε

where S is the start symbol.

Example 2: Design a CFG for the language.
L = {aⁿb²ⁿ| n ≥ 0}
At n=0, ε is a valid string for the above language. The production for this is,
S → ε
It can be seen that there are double the number of b’s as a’s. The production is,
S → aSbb
So the grammar is,
S → aSbb | ε
where S is the start symbol.

Example 3: Design a CFG for the language, L over {0,1} to generate all possible strings of even length.

Consider number 0 as even. The string of length 0 is ε. The corresponding production is,
S → ε
An even length is of length 2n contains one or more repetitions of 00, 01, 10 or 11. The corresponding production is,
S → 00S|01S|10S|11S

Thus the grammar is,
S → 00S|01S|10S|11S|ε

Example 4: Design a CFG for the language, L over {0,1} to generate all the strings having alternate sequence of 0 and 1.

The minimum string length in L is 2. The strings are 01 or 10.
If a string begins with 01, then it should follow a repetition of 01 and terminate with either 01 or 0.
If a string begins with 10, then it should follow a repetition of 10 and terminate with either 10 or 1.
The grammar will be,
S → 01|10|01A|10B
A → 01A|0|01
B → 10B|1|10

Example 5: Write a CFG for the regular expression.
a*b(a|b)*

On analysing this regular expression, we can see that the strings start with any number of a’s, followed by a ’b’ and may end with a combination of a’s and b’s.
The CFG can be written as:
S → AbB
A → aA|ε
B → aB|bB|ε

For example, using the above productions:

S ⇒ AbB
⇒ aAbB
⇒ aAbaB
⇒ aaAbaB
⇒ aaAbabB
⇒ aabab
aabab is string belonging to the above CFL.

Example 6: Write a CFG which generates strings of equal number of a’s and b’s.
The CFG is
S → aSbS|bSaS|ε

For example, using the above productions:
S ⇒ bSaS
⇒ bbSaSaS
⇒ bbaSbSaSaS
⇒ bbaSbaSbSaSaS
⇒ bbababaa
Note that above string contains equal number of a’s and b’s.

Example 7: Design a CFG for the regular expression.
(a|b)*
The CFG is,
S → aS
S → bS
S → ε
That is,
S → aS|bS|ε
where S is the start symbol.

Example 8: Design a CFG for the language.
L(G) = {ww^R|w ∈ {0, 1}* }

The CFG is,
S → 0S0|1S1|ε
where S is the start symbol.
[In the above, w^R means reverse of string w.]

For example, using the above productions:
S ⇒ 0S0
⇒ 00S00
⇒ 001S100
⇒ 001100

Example 9: Design a CFG for the language.
L = {aⁿb^m| n 6 ≠ m}

Case 1: For n>m,
The language is
L = {aⁿb^m| n > m}

The CFG is,
S₁ → AS₁
S₁ → aS₁b|ε
A → aA|a

Case 2: For n<m,
The language is:
L = {aⁿb^m| n < m}

The CFG is,
S₂ → S₂B
S₂ → aS₂b|ε
B → bB|b

Combining Case 1 and Case 2, we get,
S → S₁|S₂

Thus the CFG is,
S → S₁|S₂2
S₁ → AS₁
S₁ → aS₁b|ε
A → aA|a
S₂→ S₂B
S₂ → aS₂b|ε
B → bB|b
where S is the start symbol.

Example 10: Design a CFG for the language.
L = { (0ⁿ1ⁿ| n ≥ 0) ∪ (1ⁿ0ⁿ| n ≥ 0) }

We can write it as,
L = L₁ ∪ L₂

Case 1:
Consider L1,
L₁ = { 0ⁿ1ⁿ| n ≥ 0 }

The CFG is,
S₁ → 0S₁1|ε

Case 2:
Consider L2,
L₂ = { 1ⁿ0ⁿ| n ≥ 0 }

The CFG is,
S₂ → 1S₂0|ε

Then we have L = L₁ ∪ L₂
Combining above two cases, we get the CFG as,
S → S₁|S₂

Thus the complete CFG is,
S → S₁|S₂
S₁ → 0S₁1|ε
S₂ → 1S₂0|ε
where S is the start symbol.

Example 11: Design a CFG for the language, L
L = { aⁿb²ⁿ| n ≥ 0 }

The CFG is,
S → aSbb|ε

Example 12: Write a CFG for the language.
L = { a²ⁿb^m| n > 0, m ≥ 0 }

From the above we can say that L is the set of strings starting with even number of a’s followed by any number of b’s. There is no ’a’ in the string after first ’b’ is encountered. Also there is no ’b’ before any ’a’ in the string.
The CFG is,
S → aaAB
A → aaA|ε
B → bB|ε
where S is the start symbol.

Example 13: Write a CFG for the language.
L = {aⁿb²ⁿc^m| n, m ≥ 0}

This means strings start with ’a’ or ’c’, but not with a ’b’.
If the string starts with ’a’, then number of a’s must follow b’s, and the number of b’s is twice than number of a’s.
If the string starts with ’c’, it is followed by any number of c’s.
There is no ’a’ after any ’b’ or any ’c’.
There is no ’b’ after any ’c’.
There is no ’b’ or ’c’ after any ’a’.
There is no ’c’ after any ’b’.
Thus the CFG is,
S → AB
A → aAbb|ε
B → cB|ε
where S is the start symbol.

Example 14: Design a CFG for the language.
L = {aⁿb^mc^2m| n, m ≥ 0}

The CFG is
S → AB
A → aA|ε
B → bBcc|ε

Example 15: Design a CFG for the language, L = {wcw^R|w ∈ (a, b)*}
The CFG is
S → aSa
S → bSb
S → c
where S is the start symbol.