Scribd
Upload
24 views5 pages

Toc Assignment 2 Part2

Chapter 2(Part 2) covers various topics related to finite automata, including the differentiation between DFA and NFA, closure properties of regular languages, and the conversion of NFA to DFA. It includes tasks such as designing NFAs for specific languages and proving the equivalence of DFA and NFA. Additionally, it references model questions from previous years for practice.

Uploaded by

simantakasaju
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
24 views5 pages

Toc Assignment 2 Part2

Chapter 2(Part 2) covers various topics related to finite automata, including the differentiation between DFA and NFA, closure properties of regular languages, and the conversion of NFA to DFA. It includes tasks such as designing NFAs for specific languages and proving the equivalence of DFA and NFA. Additionally, it references model questions from previous years for practice.

Uploaded by

simantakasaju
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Chapter 2(Part 2)

1. Differentiate between DFA and NFA.


2. Explain the closure properties of Regular languages(Difference,
Homomorphism, reversal Homomorphism)
3. Prove that for each NFA there is an equivalent DFA.
4. Design an NFA over {a,b} that accepts strings having ‘aa’ as a substring.
5. Determine the NFA for regular expression a(a+b) *
6. Construct the e-NFA for the regular expression (0+1)*(0+1) .
7. Determine an NFA accepting the language L= {a*U b* }
8. Design an NFA with ∑ = {0, 1} accepts all strings in which the third symbol
from the right end is always 0.
9. Determine an NFA accepting all strings over {0,1} which end in 1 but does not
contain the substring 00.
10.Prove that the power of DFA and NFA is the same. i.e. every DFA is a unique
type of NFA.
11.Find the equivalent regular expressions of the following Finite automata using
Arden’s theorem.

a.

b.

c.

1
Prepared by: Er. Simanta kasaju
d.

e.

f.

2
Prepared by: Er. Simanta kasaju
g.

12. Covert NFA into DFA

a.

b. First design an NFA and convert it into DFA.L={the set of all strings
over (0,1) that ends with ‘1’}
c. First design an NFA accepting {ab, ba} and use it to find a DFA
accepting it.
d.

3
Prepared by: Er. Simanta kasaju
Q\∑ a b

A A, B C

B A B

*C - A,B

e.

f.

13. From model question

a. 2015 spring 7(a)


b. 2016 spring 1(b)
c. 2016 fall 1 (a)
d. 2017 spring 1(b)
e. 2018 spring 2(a)
f. 2018 fall 1(b)
g. 2019 fall 1(a) ,7(a)
h. 2020 fall 2(a)
i. 2022 fall 2(a)
j. 2023 1(b),2(a)

14. Do it

4
Prepared by: Er. Simanta kasaju
5
Prepared by: Er. Simanta kasaju

You might also like