RV Educational institutions
RV Institute of Technology and Management
(Affiliated to Visvesvaraya Technological University , Belagavi & Approved by AICTE, New Delhi)
Chaitanya Layout , JP Nagar 8th Phase , Kothanur, Bengaluru-560076
DEPARTMENT OF INFORMATION SCIENCE & ENGINEERING
Assignment –1 (submission date: 16th October 2024 )
Sem V (ISE) Subject Title Theory of Computation
Sub Code BCS503 Name of the Faculties Dr. Vinoth Kumar M
CO1 Apply the fundamentals of automata theory to write DFA, NFA, Epsilon-NFA, PDA,
TM and conversion between them.
CO2 Prove the properties of regular languages using regular expressions
CO3 Design context-free grammars (CFGs) and pushdown automata (PDAs) for formal
languages
CO4 Design Turing machines to solve the computational problems
Course
Q. Questions
No Outcomes
1 Define the following with example CO1
a) String b) Language c) Alphabet d) Power of an alphabet
2 Design DFSM to accept each of the following languages
a) L = { W Ꜫ {0, 1}* : W has 001 as a substring; CO1
b) L = { W Ꜫ {a, b}* : W has even number of a’s and even number b’s.
3 Consider the following NFA with
δ a b
➔ p {r} {q} { p, r }
CO1
q ɸ {p} ɸ
r* { p, r } {r} {p}
(i) Compute the closure for each state
(ii) Convert the automaton to DFA
4 Convert the following NFA into its equivalent DFA
CO1
5 Convert the following NFA into its equivalent DFA
CO1
6 State and prove that pumping lemma theorem for Regular expression. Show
CO2
that L = {an bn | n >= 0 } is not regular
7 Show that for every RE there is an equivalent FSM
CO2
8 Prove that regular languages are closed under intersection, complement and
CO2
difference.
8 Construct FSM for the following regular expression
(i) (b + (ab))* (ii) ab (a +b)*
CO2
(iii) (babb* + a)* (iv) (b + ) (ab)* (a + )
9 Obtain the regular expression for the finite state machine given below.
CO2
10. Obtain the regular expression for the finite state machine given below.
CO2
