Tag: Context Free Grammar

Algorithm To Decide Whether CFL Is Finite

Theory of Automata & Computation

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.

 

In this article, we will discuss a decision algorithm of CFL.

 

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

 

PRACTICE PROBLEMS BASED ON DECIDING WHETHER CFL IS FINITE-

 

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.

Algorithm To Decide Whether CFL Is Empty

Theory of Automata & Computation

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.

 

In this article, we will discuss a decision algorithm of CFL.

 

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 | Context Free Language

Theory of Automata & Computation

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).

 

Read More- Grammar Ambiguity

 

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.