UNIT I - AUTOMATA AND REGULAR EXPRESSION

Course Objective - Cob1: To understand formal languages and finite Automata.

Course Outcome - CO1: Construct automata, regular expression for any pattern.
Bloom’s Taxonomy Level: K1, K2, K3, K4

Part A

S.No. Question BTL*

Define the terms (i) Automata Theory (ii) Automata

(i) Automata Theory: It is a theoretical branch of computer science
developed by mathematician to initiate certain features of man,
1. completing calculations more quickly and reliably. K1
(ii) Automata: Automata theory deals with the logic of computation
with respect to simple machines referred to as automata.

Define alphabet, string, empty string, length of a string. K2

 Alphabet: finite, non-empty set of symbols.
Example: Σ= {0,1}, the binary alphabet
 String: finite sequence of symbols chosen from some alphabet.
2.
Example: 010001 is a string from binary alphabet {0,1}.
 Empty string: string with zero occurrences of symbols.
Example: {ε}
 Length of a string: number of symbols in the string.
Example: if string w=010001, length of the string, |𝑤|is 6.
Define Finite Automaton.
Finite Automata is a computational device which has finite amount of
memory, states and the number of states. It is denoted by a 5- tuple
(Q, Σ, δ, q0, F).
where,
3. K1
 Q is the finite set of states,
 Σ is a finite input alphabet,
 q0 in Q is the initial state,
 F is the set of final states and
 δ is the transition mapping function.

Define the concatenation of two strings.

Suppose x and y are two strings then the concatenation of x and y is
xy or yx.
Ex: if x = 0011 and y = 1100 then
K1
4. xy = 00111100 and
yx = 11000011

1
 Define Transition diagram
It is a directed graph which can be constructed as follows:
 There is a node for each state in Q, which is represented by the circle.
5. K1
 There is a directed edge from node q to node p labeled a if δ(q, a) = p.
 In the start state, there is an arrow with no source.
 Accepting states or final states are indicating by a double circle.

Define ε-closure and find the same for the five FA.
ε-close a state q by following all transitions out of q that are labeled ε.
However, when we get to other states by following ε, we follow the ε-
transitions out of those states and so on.

6. K4

ε-closure (1) = {1, 2, 3, 4, 6}

ε-closure (2) = {2, 3, 6}
ε-closure (3) = {3, 6}
ε-closure (4) = {4}
ε-closure (5) = {5, 7}
ε-closure (6) = {6}
ε-closure (7) = {7}
How does the DFA accept the string bbab?

7. Proof K2
1. Start in state q0
2. Read b, follow transition from q0 to q1.
3. Read b, follow transition from q1 to q1.
4. Read a, follow transition from q1 to q2.
5. Read b, follow transition from q2 to q1.
6. Accept because the DFA is in an accept state q1 at the end of the input.
2
 Construct a DFA that accepts all strings from the language L = {a}

8. K2

Write any two valid strings for the given DFA and its path.

9. K4

Valid strings are w = {00010, 10110}

0 0 0 1 0
Path for w = 00010 is: 𝑞0 → 𝑞2 → 𝑞2 → 𝑞2 → 𝑞1 → 𝑞1
1 0 1 1 0
Path for w = 10110 is: 𝑞0 → 𝑞0 → 𝑞2 → 𝑞1 → 𝑞1 → 𝑞1
Formally represent the following NFA with its transition table

NFA = ({q0, q1, q2}, {0,1}, δ, q0, {q2})

10. K2

Draw a DFA which accepts 011 as substring.

11.

State the difference between NFA and DFA.

S.No DFA NFA

3
 The transition from a state is to The transition from a state is
a single particular next state for to a multiple next state for
1
each input symbol. Hence, it is each input symbol. Hence, it
called deterministic. is called non-deterministic.

Empty string transitions are not NFA permits empty string

2 allowed in DFA. transition called as epsilon
transition (ε -NFA). K2
12.
Backtracking is allowed in DFA Backtracking is not possible
3
in NFA.

A string is accepted by a DFA, A string is accepted by a

if it transits to a final state. NFA, is at least one of all
4
possible transitions ends in a
final state.

Define a language of an NFA and DFA

 Language of an NFA: If A = (Q, ∑, δ, q0, F) is an NFA then

13. K1
 Language of an DFA: If A = (Q, ∑, δ, q0, F) is an NFA then

That is, the language of A is the set of strings w that take the start state q0
to one of the accepting states.
Define regular expression

It is a sequence of character that defines a search pattern used for

‘r + s’ is equivalent to L1 ∪ L2
pattern matching. If ‘r’ and ‘s’ are RE denoting the language L1 and L2 then
14. 

 ‘r s’ is equivalent to L1 L2
 ‘r*’ is equivalent to L1* (closure)

Differentiate L* and L+
 L* denotes Kleene closure. If L is a set of symbols or characters
then L* is the set of all strings over symbols in L, including the
15.
empty string ε Eg. 1* = {ε,1,11,111, 1111…}
+
L denotes the positive closure. It is the set of all symbols / character in the
set L except the empty string Eg. 1+ = {1,11, 111……}
Name any four closure properties of Regular languages.
4
 a) The union of two regular language is regular
16.
b) The intersection of two regular languages is regular
c) The complement of regular language is regular
d) The closure operation on a regular language is regular

Find the language accepted by the following automaton.

17.
The r.e that can be obtained from given DFA is
r.e = 0* 1*

Describe the following by regular expression.

L1 = the set of all strings of 0’s and 1’s ending in 00
L2 = the set of all strings of 0’s and 1’s beginning with 0 and ending
18 with 1

-> r1 = (0+1) *00

-> r2 = 0(0+1) *1

Write down the relationship between FA and regular expression

19

Is it true that the language accepted by any NFA is different from the
regular language? Justify your answer.
No, any language accepted by DFA, NFA,ε-NFA is called a regular
20 language.
For any Finite Automaton we can construct an equivalent regular
expression

5
 Part B

S.No. Question BTL*

 Design a DFA with ∑ = {0, 1} accepts those string which starts with 1 and
ends with 0. (8)
1. K4
 Design a DFA with ∑ = {a, b} accepts those string which ends with abba. (8)
 Design a DFA with ∑ = {a, b} accepts those string which ends with abaa. (8)
 Construct a substring 011with DFA ∑ = {0, 1} (8)

 Design a NFA with ∑ = {0, 1} accepts those string which starts with 1 and
2. ends with 0. (8) K4
 Design a NFA with ∑ = {a, b} accepts those string which ends with abba. (8)
 Design a NFA with ∑ = {a, b} accepts those string which ends with abaa. (8)
 Construct a substring 011with NFA ∑ = {0, 1} (8)

Construct the NFA for the following ε-NFA

3. K4

Construct a DFA for the following NFA. (16 marks)

4. K4

6
5.

Convert the given ε-NFA into DFA and validate. (16 Marks)

6. K4

Convert the given ε-NFA into DFA and validate. (16 Marks)

7. K4

Diagram only:
 Construct NFA for the regular expression (10 + 2*)1.
 Construct NFA for the regular expression r = 1*0 +0.
 Construct NFA for the regular expression ((01 + 001) *0*) *.

8.
 Construct DFA for the regular expression (b|a) * baa.
 Construct DFA for the regular expression r = (a*+b*) *.
 Construct DFA for the regular expression r = (a / b ) *.
 Construct DFA for the regular expression r = (0+1)*. 1 . (0 + 1) *

*Bloom’s Taxonomy Level