Category: Theory of Automata & Computation

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.

DFA Solved Examples | How to Construct DFA

Theory of Automata & Computation

Construction Of DFA-

 

Before you go through this article, make sure that you have gone through the previous article on Type-01 Problems.

 

Type-02 Problems-

 

In Type-02 problems, we will discuss the construction of DFA for languages consisting of strings starting with a particular substring.

 

Steps To Construct DFA-

 

Following steps are followed to construct a DFA for Type-02 problems-

 

Step-01:

 

  • Determine the minimum number of states required in the DFA.
  • Draw those states.

 

Use the following rule to determine the minimum number of states-

 

RULE

Calculate the length of substring.

All strings starting with ‘n’ length substring will always require minimum (n+2) states in the DFA.

 

Step-02:

 

  • Decide the strings for which DFA will be constructed.
  • The method for deciding the strings has been discussed in this Video.

 

Step-03:

 

  • Construct a DFA for the strings decided in Step-02.

 

Remember the following rule while constructing the DFA-

 

RULE

While constructing a DFA,

  • Always prefer to use the existing path.
  • Create a new path only when there exists no path to go with.

 

Step-04:

 

  • Send all the left possible combinations to the dead state.
  • Do not send the left possible combinations over the starting state.

 

PRACTICE PROBLEMS BASED ON CONSTRUCTION OF DFA-

 

Problem-01:

 

Draw a DFA for the language accepting strings starting with ‘ab’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = ab(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “ab”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • ab
  • aba
  • abab

 

Step-03:

 

The required DFA is-

 

Problem-02:

 

Draw a DFA for the language accepting strings starting with ‘a’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = a(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “a”.
  • So, length of substring = 1.

 

Thus, Minimum number of states required in the DFA = 1 + 2 = 3.

It suggests that minimized DFA will have 3 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • a
  • aa

 

Step-03:

 

The required DFA is-

 

Problem-03:

 

Draw a DFA for the language accepting strings starting with ‘101’ over input alphabets ∑ = {0, 1}

 

Solution-

 

Regular expression for the given language = 101(0 + 1)*

 

Step-01:

 

  • All strings of the language starts with substring “101”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 2 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 101
  • 1011
  • 10110
  • 101101

 

Step-03:

 

The required DFA is-

 

Problem-04:

 

Draw a DFA that accepts a language L over input alphabets ∑ = {0, 1} such that L is the set of all strings starting with ’00’.

 

Solution-

 

Regular expression for the given language = 00(0 + 1)*

 

Step-01:

 

  • All strings of the language starts with substring “00”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 00
  • 000
  • 00000

 

Step-03:

 

The required DFA is-

 

Problem-05:

 

Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is the set of all strings starting with ‘aa’ or ‘bb’.

 

Solution-

 

Regular expression for the given language = (aa + bb)(a + b)*

 

Step-01:

 

Minimum number of states required in the DFA = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • aa
  • aaa
  • aaaa
  • bb
  • bbb
  • bbbb

 

Step-03:

 

The required DFA is-

 

Problem-06:

 

Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is the set of all strings starting with ‘aba’.

 

Solution-

 

Regular expression for the given language = aba(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “aba”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 2 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • aba
  • abaa
  • abaab
  • abaaba

 

Step-03:

 

The required DFA is-

 

Also Read- Converting DFA to Regular Expression

 

To gain better understanding about Construction of DFA,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Minimization of DFA

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Construction of DFA | DFA Solved Examples

Theory of Automata & Computation

Construction Of DFA-

 

In this article, we will learn the construction of DFA.

 

Type-01 Problems-

 

In Type-01 problems, we will discuss the construction of DFA for languages consisting of strings ending with a particular substring.

 

Steps To Construct DFA-

 

Following steps are followed to construct a DFA for Type-01 problems-

 

Step-01:

 

  • Determine the minimum number of states required in the DFA.
  • Draw those states.

 

Use the following rule to determine the minimum number of states-

 

RULE

Calculate the length of substring.

All strings ending with ‘n’ length substring will always require minimum (n+1) states in the DFA.

 

Step-02:

 

  • Decide the strings for which DFA will be constructed.
  • The method for deciding the strings has been discussed in this Video.

 

Step-03:

 

  • Construct a DFA for the strings decided in Step-02.

 

Remember the following rule while constructing the DFA-

 

RULE

While constructing a DFA,

  • Always prefer to use the existing path.
  • Create a new path only when there exists no path to go with.

 

Step-04:

 

  • Send all the left possible combinations to the starting state.
  • Do not send the left possible combinations over the dead state.

 

PRACTICE PROBLEMS BASED ON CONSTRUCTION OF DFA-

 

Problem-01:

 

Draw a DFA for the language accepting strings ending with ’01’ over input alphabets ∑ = {0, 1}

 

Solution-

 

Regular expression for the given language = (0 + 1)*01

 

Step-01:

 

  • All strings of the language ends with substring “01”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 1 = 3.

It suggests that minimized DFA will have 3 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 01
  • 001
  • 0101

 

Step-03:

 

The required DFA is-

 

 

Problem-02:

 

Draw a DFA for the language accepting strings ending with ‘abb’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = (a + b)*abb

 

Step-01:

 

  • All strings of the language ends with substring “abb”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 1 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • abb
  • aabb
  • ababb
  • abbabb

 

Step-03:

 

The required DFA is-

 

Problem-03:

 

Draw a DFA for the language accepting strings ending with ‘abba’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = (a + b)*abba

 

Step-01:

 

  • All strings of the language ends with substring “abba”.
  • So, length of substring = 4.

 

Thus, Minimum number of states required in the DFA = 4 + 1 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • abba
  • aabba
  • ababba
  • abbabba
  • abbaabba

 

Step-03:

 

The required DFA is-

 

 

Problem-04:

 

Draw a DFA for the language accepting strings ending with ‘0011’ over input alphabets ∑ = {0, 1}

 

Solution-

 

Regular expression for the given language = (0 + 1)*0011

 

Step-01:

 

  • All strings of the language ends with substring “0011”.
  • So, length of substring = 4.

 

Thus, Minimum number of states required in the DFA = 4 + 1 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 0011
  • 00011
  • 000011
  • 0010011
  • 00110011

 

Step-03:

 

The required DFA is-

 

 

Also Read- Converting DFA to Regular Expression

 

To gain better understanding about Construction of DFA,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Construction of DFA | Type-02 Problems

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.