Theory of Computation - Context Free Grammars (CFG) and Context Free Languages (CFL)

In this tutorial we will introduce context free grammars and context free language. Context free languages have great practical significance. CFLs are used by the compiler in the parsing phase as they define the syntax of a programming language and are used in many editors.

There are four important components in a grammatical description of a language:

There is a set of symbols that form the strings of the language being defined. They are called terminal symbols, represented by V_t.
There is a finite set of variables, called non-terminals. These are represented by V_n.
One of the variable represents the language being defined; it is called the start symbol. It is represent by S.
There are finite set of rules called productions that represent the recursive definition of a language. Each production consists of:
1. A variable that is being defined by the production. This variable is often called the head of the production.
2. The production symbol ->.
3. A string of zero or more terminals and variable.

Formal definition

A context-free grammar (CFG) is a 4-tuple G=(V_n, V_t, S, P), where V_n and V_t are disjoint finite sets, S is an element of V_n, and P is a finite set of formulas of the form A -> α, where A ϵ V_n and α ϵ (V_n U V_t)*.

Iterative Derivation

If α -> β is a production of P in CFG and a and b are strings in (V_n, V_t)*, then
Aαb =>_G aβb
We say that the production α -> β is applied to the string aαb to obtain aβb or we say that aαb directly drives aβb.
Now suppose α₁, α₂, α₃, …., α_m are string in (V_n U V_t)*,
m >= 1 and α₁ =>_G α₂, α₂ =>_G α₃, …., α_m-1 =>_Gα_m
Then we say that α₁ =>_G^* α_m, i.e. , we say α₁, derives α_m in grammar G. If α derives β by exactly i steps, we say α=>_Gⁱ β.

The Language Generated by a CFG

Let G = (V_n, V_t, S, P) be a CFG. The language generated by G is
L(G) = {x ϵ Σ* | S =>_G^*x}
A language L is a context-free language(CFL) if there is a CFG G so that L = L(G).

Bacos Naur Form (BNF)

Note: Join free Sanfoundry classes at Telegram or Youtube

CFGs are generally written in BNF. In this notation we combine multiple productions with same non-terminal on the left hand side as follows:
S -> bA/aB

Note: We always begin with the start symbol S.

Example:Write a CFG for the language
L = {wcw^r | w ϵ (a, b)*}
Solution

Let G be a CFG for the language L. G = (V_n, V_t, P, S)
Here, V_n = {S}
V_t = {a, b, c}
And P is given by
S -> aSa
S -> bSb
S -> c
Let us check that abbcbba can be derived from the given CFG.
S =>aSa (use the production S -> aSa)
=> abSba (use S -> bSb)
=> abbSbba (use S ->bSb)
=> abbcbba (use S->c)
So string abbcbba can be derived from given CFG.

Eample 2: Write a CFG for the regular expression r = 0*1(0+1)*
Solution

To generate a grammar we divide the regular expression into 3 parts 0*, 1, (0 + 1)* represented by 3 non-terminal symbols.
Let the CFG be G = (V_n, V_t, P, S)
Here, V_n = {S, A, B}
V_t = {0, 1}
And productions P are defined as
S -> A1B
S -> 0A/ϵ
S -> 0B/1B/ϵ
Let us test the grammar against an example : 001011
S => A1B
=> 0A10B
=> 00A101B
=> 001011

Question 1: Write a CFG, which generates palindrome for binary numbers.
Solution

The grammar will generate palindrome for binary numbers, that is 00, 010, 001100, …
Let G be the CFG G = (V_n, V_t, P, S)
V_n = {S}
V_t = {0, 1}
And production rule P is defined as
S -> 0S0/ 1S1
S -> 0/1/ϵ

Question 2: Write a CFG for language L = {0ⁱ1^j2^k | k <= i or k <= j}
Solution

We can think of L as union of two language,
L = L₁ U L₂
Where L₁ = {0ⁱ1^j2^k | k <= i} And L₁ = {0ⁱ1^j2^k | k <= j} Let us assume that CFG for L₁ is G₁
G₁ = (V_n, V_t, P₁, S₁)
V_n = {S₁, X, Y}
V_t = {0, 1}
And P₁ is defined as
S₁ -> S₁2/0Y2
Y -> C/0Y/ϵ
C -> 1C/ϵ
Let us assume that CFG for L₂ is G₂
G₂ = (V_n, V_t, P₂, S₂)
V_n = {S₂, A, B}
V_t = {0, 1}
And P₂ is defined as
S₂ -> AB
A -> 0A/ϵ
B -> 1B2/1B/ϵ
We can define CFG for L(since L = L₁ U L₂)
Let us assume that CFG for L is G
G = (V_n, V_t, P , S)
V_n = { S₁, S₂, X, Y, A, B}
V_t = {0, 1}
P is defined as
S -> S₁/S₂
S₁ -> S₁2/0Y2
Y -> C/0Y/ϵ
C -> 1C/ϵ
S₂ -> AB
A -> 0A/ϵ
B -> 1B2/1B/ϵ

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.

If you find any mistake above, kindly email to [email protected]

« Prev - Theory of Computation – Pumping Lemma for Regular Languages and its Application

» Next - Theory of Computation – Regular Grammars

Related Posts:

Recommended Articles: