Assignment II
TOC
1. Differentiate between DFA and NFA.
2. Design a DFA that accepts the strings over an alphabet {0, 1} that either start with 01 or end
with 01. Hence test your design for any two strings.
3. Design a DFA that accepts the language L = {w ε (a, b): w must have either aaa or bbb as
substring}.
4. Define configuration of DFA. Design a DFA that accepts the language L = {w ε (0, 1): w must have
both 01 and 10 as substring}. Verify your design using one accepted and one rejected string.
5. Design a DFA that accepts the language L = {x: x ε (0, 1) *| 10110 does not occur as substring in
x}. Verify your design using supporting examples.
6. Design a DFA that accepts the language over {a, b} defined by {0 0} * {1 1} *.
7. Design a DFA over {a, b} accepting strings having even number of a’s and odd number of b’s.
8. Design a DFA that accepts the language given by L = {w ε {0, 1} *: w begins with 0 and end with
10}.
9. Design a DFA that accepts the language L = {x ε (0, 1) *: 0110 occurs as a substring in x}. Verify
your design using suitable examples
10. Design a DFA over {0, 1} * accepting string having even number of 0’s and even number of 1’s.
12. Construct a NFA for language (ab*a ∪ b*aa). Verify your design using one accepted and one
11. Design a DFA that accepts the language L = {w ε (0, 1) *: |w| is the multiple of five.
rejected string.
13. Design a NFA which accepts L = {w | w ε (a, b) *: w contains either two consecutive a’s or two
consecutive b’s}.
P.S. The deadline for submission of this tutorial is 3rd of Poush, 2081.
