MMANTC
Department of Computer Engineering
Subject: TOC Unit I Submitted to Prof: Siraj Ahmad
1. Define the following terms with example –
i) DFA ii) NFA iii) epsilon NFA
2. Define the following terms with example.
i) Alphabet iii) Regular Language
ii) String iv) Regular Expression
3. Give formal definitions for the following.
i) Deterministic finite automata ii) Moore machine
4. Compare DFA and NFA.
5. Compare Moore machine and Mealy machine.
6. Construct DFA to accept String end with 10
7. Construct DFA for checking “whether a string over alphabet {a, b} contains a
substring aba”.
8. Draw FA for the following language over {0. 1}
i) Number of 1’s is multiple of 3.
ii) Number of 1’s is not multiple of 3
9. Construct DFA for language defined by input {0, 1} where
S = (String ending with 0 always)
S = (String representing odd binary number)
S = (String over alphabets * with total nos of 0’s even)
10. Design FA which checks the divisibility by 3 for binary number input.
11. Construct DFA for the language of all string the begin and end with same symbol for
alphabet {0, 1}.
12. Design a DFA which checks the divisibility by 4 for decimal number.
13. Design Finite Automata (FA) for accepting strings over Σ ={0,1} with even numbers
of 0’s and odd number of 1’s.
14. Convert following NFA to DFA
15. Convert the given NFA– ε to an NFA to DFA. (* ε is represented as Λ)
16. Convert the given NFA– ε to an NFA to DFA.
17. Draw the transition table for Mealy machine represented by given figure and find the
output for 0101101.
18. Draw the transition table for Moore machine represented by given figure and find the
output for 0101101.
19. Convert Mealy machine to Moore machine.
20. Draw the machines given the transition and output tables.
