Subject: Theory of Computation
1. Define NFA with € transition.
2. Design FA which accepts odd number of 1’s and any number of 0’s
3. Design FA to check whether given binary number is divisible by
three
4. Design DFA to accept the strings over {0,1} with two consecutive
0’s
5. Show that for any language L*-{€} ≠ L+.
6. Using Pumping Lemma, prove that the language A = {anbn| n≥0} is
not regular
7. Explain Arden’s theorem
8. Mention Algebraic laws for regular expression
9. Convert the following DFA to Regular expression using state
elimination method
10 Convert FA to Regular Expression using Arden’s Theorem
11 Convert the following NFA to its equivalent DFA
12 Convert the following Non-Deterministic Finite Automata (NFA)
to Deterministic Finite Automata (DFA)
13 Consider a Mealy machine M = (Q, Σ, Δ, λ, μ), where:
Q = {q0, q1, q2} is the set of states,
Σ = {0, 1} is the input alphabet,
Δ = {a, b} is the output alphabet,
λ(q0, 0) = q1, λ(q0, 1) = q2, λ(q1, 0) = q1, λ(q1, 1) = q0, λ(q2, 0) = q2,
λ(q2, 1) = q0 is the transition function, and
μ(q0, 0) = a, μ(q0, 1) = b, μ(q1, 0) = b, μ(q1, 1) = a, μ(q2, 0) = a, μ(q2,
1) = b is the output function
Convert the given Mealy machine M to an equivalent Moore
machine.
14 Convert the following DFA to a regular expression
15 Design a Finite Automata from the given RE= xy + (y + xx)y* x
16 Remove epsilon from the following NFA
17 Minimize the following DFA using Myhill-Nerode Theorem.
18 Minimize the DFA using equivalence method.
