1)Difference Between DFA and NFA

1 The full form of DFA is Deterministic The full form of NFA is

Finite Automata. Nondeterministic Finite Automata
(NFA).

For each input symbol there is exactly . For each input symbol there is one or
one transition out of each state. more transition from a state on the
same input symbol.

There can be multiple final states. There can be multiple final states.

2 It is not competent in handling an Empty It is competent to handle an empty

String transition. string transition.

3 In DFA, only a sole state transition can In NFA, no particulars are required
be accomplished for each symbolic from the users.
representation of the characters.

4 It can be defined as one machine. Multiple machines execute

computational tasks at the same time.

5 In DFA, backtracking is allowed. In NFA, backtracking is not allowed.

6 In DFA, empty string transitions are not It allows empty string transition.
noticed.

7 It is tough to construct a DFA. It is easy to construct a NFA.

8 It needs more space. It needs less space.

9 The complete time needed for managing The complete time needed for
any input string in DFA is shorter than managing any input string in NFA is
NFA. larger than DFA.

10 All DFA are considered as NFA. All NFA are not considered as DFA.

2)What is the epsilon state transition?

An epsilon transition (also epsilon move or lambda transition) allows an automaton to change
its state spontaneously, i.e. without consuming an input symbol. It may appear in almost all
kinds of nondeterministic automaton in formal language theory, in particular: Nondeterministic
Turing machine.

3)Construct a DFA for the language over {0, 1}* such that it contains "000" as a
substring. AU : May-11

Ans.:
4)Construct NFA for the regular expression a*b*.
a*b* corresponds to the set of strings consisting of zero or more a's followed by zero or more
b's. a*b+a* corresponds to the set of strings consisting of zero or more a's followed by one or
more b's followed by zero or more a's.
5)What is pumping lemma
The pumping lemma for regular languages states that any long string in a regular language can
be split into three parts, where the middle part can be repeated any number of times. This
process is known as "pumping".

The technique for proving nonregularity of some language is provided by a theorem

about regular languages called pumping lemma
• Pumping lemma states that all regular languages have a special property
• If we can show that a language L does not have this property we are guaranteed that L
is not regular.
Part B

6a i)Explain the different forms of proof with examples.

ii) Prove that there exists a DFA for every ε-NFA.
Or
Construct a DFA that accepts the following
b (i) L={ x € {a,b}:|x|a = odd and |x|b = even}.
ii)Binary strings such that the third symbol from the right end is 1.

Construct a DFA that accepts the following

(ii) L={ x € {a,b}:|x|a = odd and |x|b = even}.

A Deterministic Finite automaton (DFA) is a five tuples

M=(Q, Σ, δ,q0,F)
Where,
 Q : Finite set called states.
 Σ : Finite set called alphabets.
 δ : Q × Σ → Q is the transition function.
  q0 ϵ Q is the start or initial state.
 F : Final or accept state.

ACCEPTED STRING

FOR aa

For bb

For abab
For baba
For baab

Construct a DFA that accepts the following

Binary strings such that the third symbol from the right end is 1.
 Discuss the basic approach to convert from NFA to regular
7a
expression. Illustrate with an example.
Or
What is Regular Expression? Write a regular expression for set
b
of strings that consists of alternating 0’s and 1’s..

What is Regular Expression? Write a regular expression for set of strings that consists of
alternating 0’s and 1’s..
Regular Expression
A regular expression (regex) is a sequence of characters that describes a pattern to match in
text. It's a way to represent a language that can be accepted by a finite automaton.
Regular expressions are symbolic notations used to define search patterns in strings. They
describe regular languages and are commonly used in tasks such as validation, searching, and
parsing
Application of regular expressions
 To search for strings of text in a file
 To validate input
 To perform "find" or "find and replace" operations on strings
A regular expression represents a regular language if it follows these rules:
1. ϵ (epsilon) is a regular expression representing the language {ϵ} (the empty string).
2. Any symbol ‘a’ from the input alphabet Σ is a regular expression, representing the
language {a}.
3. Union (a + b) is a regular expression if a and b are regular expressions, representing
the language {a, b}.
4. Concatenation (ab) is a regular expression if a and b are regular expressions.
5. Kleene star (a) is a regular expression*, meaning zero or more occurrences of ‘a’,
forming a regular language.
Regular
Description Regular Expression Languages

Set of vowels `(a e

{a, ab, abb,

‘a’ followed by
ab* abbb,
0 or more ‘b’
abbbb, ...}

Any number of {ε, a, aou, aiou,

vowels followed b, abcd, ...} (ε
[aeiou]*[bcdfghjklmnpqrstvwxyz]*
by any number represents
of consonants empty string)

Representation of Regular expression

 A regular expression can be defined as a pattern sequence that defines a string
 A regular expression is a string on Σ, where Σ is the input alphabet
 Regular expressions are built up using the operations union (+), concatenation, and star
(*)
Examples of regular expressions
 a* means zero or more occurrences of a
 a+ means one or more occurrences of a
 (a+b*)* and (a+b)* are equivalent regular expressions
Regular Expressions Vs Languages
The symbols of the regular expressions are distinct from those of the languages. These
symbols are given below −

Operators in Regular Expression

There are two binary operations on regular expressions (+ and ·) and one unary operator (*)

Operations Performed on Regular Expressions

The union of two regular languages, L1 and L2, which are represented using L1 ∪ L2, is also
1. Union

regular and which represents the set of strings that are either in L1 or L2 or both.
Example:
L1 = (1+0).(1+0) = {00 , 10, 11, 01} and

then L1 ∪ L2 = {∈, 00, 10, 11, 01, 100}.

L2 = {∈ , 100}

2. Concatenation
The concatenation of two regular languages, L1 and L2, which are represented using L1.L2 is
also regular and which represents the set of strings that are formed by taking any string in L1
concatenating it with any string in L2.
Example:
L1 = { 0,1 } and L2 = { 00, 11} then L1.L2 = {000, 011, 100, 111}.
3. Kleene closure
If L1 is a regular language, then the Kleene closure i.e. L1* of L1 is also regular and represents
the set of those strings which are formed by taking a number of strings from L1 and the same
string can be repeated any number of times and concatenating those strings.
Example:
L1 = { 0,1} = {∈, 0, 1, 00, 01, 10, 11 …….} , then L* is all strings possible with symbols 0
and 1 including a null string.
Write a regular expression for set of strings that consists of alternating 0’s and 1’s..

Let L be the language of 00's and 11's in alternate positions, where

L={ϵ,0,1,01,10,01010,…}.

1. ∈ (no input, 0 and 1)

Strings that will be acceptable by regular expression with alternate 0’s and 1’s –

2. 010101….. (string that starts with 0 followed by 1 and so on).

3. 101010….. (string that starts with 1 followed by 0 and so on).
Now, a regular expression for set of all strings consisting of alternate 0’s and 1’s would be

where it can accept ∈, 01, 0101, 010101…..etc but this restricts the string as it can always
(01)*

Again, the expression (10)* will accept ∈, 10, 1010, 101010….etc but this too restricts string
begin with 0 only.

as it can always begin with 1 only.

So, we introduce 1(01)* and0(10)*
to meet gap in respective cases. While 1(01)* breaks the restriction of string starting with 0,
0(10)* breaks same for string starting with 1. So, the final expression is –
(0+1)*0(0+1)*1(0+1)*1(0+1)*1(0+1)*

Figure –Finite Automata of Regular Expression for alternate 0’s and 1’s

Part C (1×14 = 14 Marks)

 8a
Construct minimized automata for the following automata to define the same
language.

a b
🡪q0 q1 q0
q1 q0 q2
q2 q3 q1
*q3 q3 q0
q4 q3 q5
q5 q6 q4
q6 q5 q6
q7 q6 q3

Or
Construct a minimized DFA from the regular expression
B (i) 0*(01)(0/111)*

Construct minimized automata for the following automata to define the same language.

a b
🡪q0 q1 q0
q1 q0 q2
q2 q3 q1
*q3 q3 q0
q4 q3 q5
q5 q6 q4
q6 q5 q6
q7 q6 q3

Answer

DFA
Deterministic finite automata (or DFA) are finite state machines that accept or reject
strings of characters by parsing them through a sequence that is uniquely determined by
each string. The term “deterministic” refers to the fact that each string, and thus each
state sequence, is unique.

How does a DFA work?

1. A DFA has a finite number of states, an alphabet, and a transition function
 2. The DFA starts in an initial state
3. The DFA reads a string of symbols, one at a time
4. The DFA uses the transition function to determine the next state based on the input
symbol
5. The DFA accepts the string if it reaches an accepting state

Minimization of DFA
DFA minimization stands for converting a given DFA to its equivalent DFA with minimum
number of states. DFA minimization is also called as Optimization of DFA and uses
partitioning algorithm.

Steps for Minimization

Suppose there is a DFA D < Q, Δ, q0, Δ, F > which recognizes a language L. Then the
minimized DFA D < Q’, Δ, q0, Δ, F’ > can be constructed for language L as:
Step 1: Remove steps which are unreachable from initial states.
Step 2: We will divide Q (set of states) into two sets. One set will contain all final states and
other set will contain non-final states. This partition is called P0.
Step 3: Initialize k = 1
Step 4: Find Pk by partitioning the different sets of Pk-1. In each set of Pk-1, we will take all
possible pair of states. If two states of a set are distinguishable, we will split the sets into
different sets in Pk.
Step 5: Stop when Pk = Pk-1 (No change in partition)
Step 6: All states of one set are merged into one. No. of states in minimized DFA will be equal
to no. of sets in Pk.

Solution:

Transition table for above automata.

🡪q0 q1 q0
q1 q0 q2
q2 q3 q1
*q3 q3 q0
q4 q3 q5
q5 q6 q4
q6 q5 q6
q7 q6 q3

State Input = a Input = b

->q0 Initial state q1 Q0

 q1 Q0 Q2

q2 Q3 q1

q3 Final state Q3 Q0

Q4 Q3 Q5

Q5 Q6 Q4

Q6 Q5 Q6

Q7 Q6 Q3

Transition diagram

Step 01: Remove steps which are unreachable dead states from initial states.

States q4,q5,q6,q7 cannot reach from initial state q0 so there dead states so they are
removed
Trantition table after removing dead state

State Input = a Input = b

->q0 Initial state q1 Q0

q1 Q0 Q2

q2 Q3 q1

q3 Final state Q3 Q0

Transition diagram after removing dead state

Step 02: Split final states and non final states.

starting state q0q1

Final state q3
Minimized DFA:

State Input = a Input = b

->{q0,q1} Initial state Q0q1 Q2

{q2} Q0 Q1

{q3} Final state Q3 q1