Wayanamac Education Trust®
DONBOSCO INSTITUTE OF TECHNOLOGY
Kumbalagodu, Mysuru Road, Bengaluru–560074
www.dbit.co.inPh:+91-80-28437028/29/30Fax:+91-80-28437031
Department of Computer Science & Engineering
ASSIGNMENT
Course Name with Code: Theory of Computations (BCS503) Sem: V A, B & C
Date of Given: 18/10/24 Max Marks:10
Date of Submission: On or before 30/10/24
SI.
No GROUP - A CO RB Mar
TL ks
1. What is Automata? Discuss why study automata? Give applications of ATC. CO1 L2 10
2. Define DFSM. Design a DFSM to accept each of the following languages: CO1 L3 10
i. L={w € {0,1}* :w has 001 as a substring}
ii. L={w € {a,b}* :w has even number of a’s and even number of b’s} show that aabbaa
is accepted
iii. L={w € {a,b}* :w has odd number of a’s and even number of b’s} show that bbabaab
is accepted
iv. L={w € {0,1}* :w contains no more than one b}
3. Convert NFA to DFA CO1 L3 10
4. Convert e-NFA to Equivalent DFA CO1 L3 10
ꝺ € A B C
p Ф {p} {q} {r}
q {p} {q} {r} Ф
r {q} {r} Ф {p}
5. Define distinguishable and indistinguishable States. Minimize the following DFSM. CO2 L2, L3 10
6. Obtain a regular expression for the language CO2 L2 06
i. L= {anbm | m+n is even }
ii. L= { anbm | m>=1, n>=1, nm>=3}
GROUP - B
7. Define the following terms with examples: (i) Alphabet (ii) Power of an alphabet CO1 L1 10
(iii) Functions on Strings (iv) Symbol (v) Language (vi) Strings (vii) Relations on String
8. Explain DFA. Design a DFA CO1 L3 10
a) To accept binary numbers divisible by 5.
b) To accept Strings of a’s and b’s ending with ab or ba.
c) To accept Strings of a’s and b’s having even number of symbols.
9. Convert NFSM to DFSM CO1 L3 10
i.10. Convert e-NFA to Equivalent DFA. CO1 L2 10
11 Define Distinguishable and Indistinguishable States. Minimize the following DFSM. CO2 L3 10
12. Obtain a regular expression for the language CO2 L2 06
i. L= {a2nb2m | n>=0, m>=0 }
ii. L= { w: |w| mod 3 =0 where w€(a,b)*}
GROUP - C
13. Mention all the differences between DFA, NFA and e-NFA. CO1 L2 10
14. Define DFA. Design a DFA for the following language over ∑={a,b} CO1 L2 10
i. Set of all Strings not containing the substring “aab”
ii. Set of all Strings with exactly three consecutive a’s.
iii. Set of all Strings ending with a and b.
15. Convert NFA to DFA CO1 L3 10
16. Convert e-NFA to Equivalent DFA CO1 L3 10
17. Define Distingishable and Indistinguishable states. Minimize the following DFA. CO2 L3 10
18 Obtain regular expression for the following languages on ∑={a,b,c} CO2 L2 06
a) All strings containing exactly one a
b) All strings containing no more than three a’s
GROUP - D
19. Define a DFA CO1 L3 10
i. To accept the language L={w: na(w)mod 3=0} on ∑={a,b}}
ii. To accept language L={w: where |w|mod 3=0 where ∑={a} }
iii. To accept language L={w: na(w)mod 3≠0} on ∑={a,b}}
iv. To accept language L={w: where |w|mod 5≠0} on ∑={a}
20. Convert NFA to Equivalent DFA CO1 L3 10
21. Convert e-NFA to Equivalent DFA CO1 L3 10
22. Define Distinguishable and Indistinguishable States. Minimize the following DFA. CO2 L3 10
23. i. Obtain an NFA to accept L={ w € {a,b,c}* : x and y € {a,b,c}* and w = x abcabb y CO1 L3 10
ii. Obtain an NFA to accept the language L= {w | w € ababn or aban where n>=1}
24. a) Obtain a regular regular expression for L = {vuv : u, v € {a,b}* and |v| =2 } CO2 L2 06
b) Obtain a regular regular expression for L = {an bm: n>=4,m<=3}
