## Context Free Language-

Before you go through this article, make sure that you have gone through the previous article on Context Free Language.

We have discussed-

• Context free language is generated using a context free grammar.
• Each context free language is accepted by a Pushdown automaton.

## Algorithm To Decide Whether CFL Is Finite Or Not-

For a given CFG, there exists an algorithm to decide whether its language is finite or not.

### Step-01:

Reduce the given grammar completely by-

• Eliminating ∈ productions
• Eliminating unit productions
• Eliminating useless productions

Also Watch- How To Reduce Grammar?

### Step-02:

• Draw a directed graph whose nodes are variables of the given grammar.
• There exists an edge from node A to node B if there exists a production of the form A → αBβ.

Now, following 2 cases are possible-

### Case-01:

• Directed graph contains a cycle.
• In this case, language of the given grammar is infinite.

### Case-02:

• Directed graph does not contain any cycle.
• In this case, language of the given grammar is finite.

Also Read- Algorithm To Decide Whether CFL Is Empty

## Problem-01:

Check whether language of the following grammar is finite or not-

S → AB / a

A → BC / b

B → CC / c

## Solution-

### Step-01:

The given grammar is already completely reduced.

### Step-02:

We will draw a directed graph whose nodes will be S , A , B , C.

Now,

• Due to the production S → AB, directed graph will have edges S → A and S → B.
• Due to the production A → BC, directed graph will have edges A → B and A → C.
• Due to the production B → CC, directed graph will have edge B → C.

The required directed graph is-

Clearly,

• The directed graph does not contain any cycle.
• Therefore, language of the given grammar is finite.

## Problem-02:

Check whether language of the following grammar is finite or not-

S → XS / b

X → YZ

Y → ab

Z → XY

## Solution-

### Step-01:

The given grammar is already completely reduced.

### Step-02:

We will draw a directed graph whose nodes will be S , X , Y , Z.

Now,

• Due to the production S → XS / b, directed graph will have edges S → X and S → S.
• Due to the production X → YZ, directed graph will have edges X → Y and X → Z.
• Due to the production Z → XY, directed graph will have edges Z → X and Z → Y.

The required directed graph is-

Clearly,

• The directed graph contain cycles.
• Therefore, language of the given grammar is infinite.

Next Article- CYK Algorithm

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

## Context Free Language-

Before you go through this article, make sure that you have gone through the previous article on Context Free Language.

We have discussed-

• Context free language is generated using a context free grammar.
• Each context free language is accepted by a Pushdown automaton.

## Algorithm To Decide Whether CFL Is Empty Or Not-

 If we can not derive any string of terminals from the given grammar,then its language is called as an Empty Language.L(G) = ϕ

For a given CFG, there exists an algorithm to decide whether its language is empty L(G) = ϕ or not.

### Algorithm-

• Remove all the useless symbols from the grammar.
• A useless symbol is one that does not derive any string of terminals.
• If the start symbol is found to be useless, then language is empty otherwise not.

### Remember

The language generated from a CFG is non-empty iff the start symbol is generating.

## Example-

Consider the following grammar-

S → XY

X → AX

X → AA

A → a

Y → BY

Y → BB

B → b

Now, let us check whether language generated by this grammar is empty or not.

The given grammar can be written as-

S → aabb

X → aX

X → aa

A → a

Y → bY

Y → bb

B → b

Clearly,

• The start symbol generates at least one string (many more are possible).
• Therefore, start symbol is useful.
• Thus, language generated by the given grammar is non-empty.

 L(G) ≠ ϕ

## NOTE-

If L(G) = { ∈ } i.e.

• If the language generated by a grammar contains only a null string,
• then it is considered as non-empty.

Next Article- Algorithm To Decide Whether CFL Is Finite

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

## Context Free Grammar-

A context Free Grammar (CFG) is a 4-tuple such that-

G = (V , T , P , S)

where-

• V = Finite non-empty set of variables / non-terminal symbols
• T = Finite set of terminal symbols
• P = Finite non-empty set of production rules of the form A → α where A ∈ V and α ∈ (V ∪ T)*
• S = Start symbol

### Why Context Free Grammar Is Called So?

Context Free Grammar provides no mechanism to restrict the usage of the production rule A → α within some specific context unlike other types of grammars.

That is why it is called as “Context Free” Grammar.

### Example-01:

Consider a grammar G = (V , T , P , S) where-

• V = { S }
• T = { a , b }
• P = { S → aSbS , S → bSaS , S → ∈ }
• S = { S }

• This grammar is an example of a context free grammar.
• It generates the strings having equal number of a’s and b’s.

### Example-02:

Consider a grammar G = (V , T , P , S) where-

• V = { S }
• T = { ( , ) }
• P = { S → SS , S → (S) , S → ∈ }
• S = { S }

• This grammar is an example of a context free grammar.
• It generates the strings of balanced parenthesis.

### Applications-

Context Free Grammar (CFG) is of great practical importance. It is used for following purposes-

• For defining programming languages
• For parsing the program by constructing syntax tree
• For translation of programming languages
• For describing arithmetic expressions
• For construction of compilers

## Context Free Language-

 The language generated using Context Free Grammar is called as Context Free Language.

### Properties-

• The context free languages are closed under union.
• The context free languages are closed under concatenation.
• The context free languages are closed under kleen closure.
• The context free languages are not closed under intersection and complement.
• The family of regular language is a proper subset of the family of context free language.
• Each Context Free Language is accepted by a Pushdown automaton.

### Remember

If L1 and L2 are two context free languages, then-

• L1 ∪ L2 is also a context free language.
• L1.L2 is also a context free language.
• L1* and L2* are also context free languages.
• L1 ∩ L2 is not a context free language.
• L1′ and L2′ are not context free languages.

## Ambiguity in Context Free Grammar-

A grammar is said to be ambiguous if for a given string generated by the grammar, there exists-

• more than one leftmost derivation
• or more than one rightmost derivation
• or more than one parse tree (or derivation tree).

To gain better understanding about Context Free Grammar,

Watch this Video Lecture

Next Article- Chomsky Normal Form

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.