PART -A
1. Explain transition diagram, transition table with example.
2. Define transition function of DFA.
3. Define ε –transitions.
4. Construct a DFA to accept even number of 0’s.
5. Define Kleene closure and positive closure.
6. Construct a DFA to accept empty language.
7. Explain power of an alphabet (∑*)?
8. Write transition diagram for DFA accepting string ending with 00
defined over an alphabet ∑= {0,1}
9. Write transition diagram for DFA to accept exactly one a
defined over an alphabet ∑= {a,b}
10. Define NFA with an example.
11. Explain the different Operations on the languages.
13. Define Moore Machines.
14. Define Mealy Machines.
15. Write DFA for odd number of 1’s.
16. Write NFA for (0+1)*101(0+1)*.
17. Write DFA for (0+1)*10(0+1)*.
18. Define ɛ - closure.
19. Write NFA for (0+1)*001(0+1)*.
20. Write DFA for (0+1)*00(0+1)*.
21 Define FSM and its structure with an example.
22 Give any two comparisions between NFA and DFA
1 Write down the operations on set.
2 List any three applications of Automata Theory.
3 Define Finite Automation.
4 Define Deterministic Finite Automation.
5 Define Non-Deterministic Finite Automation.
6 Define NFA with transition.
7 Design FA which accepts odd number of 1‟s and any number of 0‟s.
8 Design FA to check whether given unary number is divisible by
three.
9 Design FA to check whether given binary number is divisible by
three.
10 Design FA to accept the string that always ends with 00.
11 Obtain the closure of states q0 and q1 in the following NFA with
transition.
12 Obtain closure of each state in the following NFA with move.
13 Explain a transition diagram.
14 Explain a transition table.
15 Explain the transition function.
16 Differentiate DFA and NFA?
17 Write notes on Moore Machine.
18 Write the formal definition of Moore Machine.
19 Short notes on Mealy Machine.
20 Write the formal definition of Mealy Machine.
21 Compare the Mealy and Moore Model?
Define
(a) Finite Automata (FA)
(b) Transition Diagram
Define ε-closure(q) with an example.
Construct a DFA for the language over {0, 1}* such that it
contains “000” as a substring.
State the difference between NFA and DFA.
Construct deterministic finite automata to recognize odd number
of 1’s and even number of 0’s?
State the relations among regular expression, deterministic finite
automata, non deterministic finite automaton and finite
automaton with epsilon transition.
Every Regular language defined by a regular expression ia also
defined by the finite automata. If a Regular language ‘L’ is accepted
by a NFA then there exists a DFA that accepts ‘L’.
Find the set of strings accepted by the finite automata.
0,1
(0+1)* or L={ε, 0, 1, 00, 01, 10, 11,. }
What is meant by DFA
Define the term Epsilon transition
What is non deterministic finite automata?
Design DFA to accept strings over ∑ = (0,1) with two consecutive 0’s
What is a finite automaton?
Write Regular Expression for the set of strings over
{0.1} that have atleast one.
Draw a Non-deterministic finite automata to accept strings containing
the substring 0101.
State the pumping lemma for regular languages.
Define the languages described by DFA and NFA.
L(DFA) = { w / δ‟(q0,w) is in F}.It is the set of strings w that take
the start state q0 to one of the accepting states.
L(NFA)= { w / δ‟(q0,w)∩F≠ }.It is the set of strings w such that
δ‟(q0,w)contains at least one accepting state.
Define extended transition function for a DFA.
The extended transition function δ‟: Qε∑ * εQ is defined as
follows.
(i) δ’(q, ε ) = q (ε - Empty)
Suppose w is a string of form xa(w= xa), wε∑*and q Q , then
δ’(q, w)= δ( δ’(q, x),a)
Give a regular expression for the set of all strings having odd
number of 1’s
RE= 1(0+11)*
Give the regular expression for the set of all strings ending in 00.
Regular expression = (0+1)*00
When two states are equivalent and distinguishable?
We say that two states p and q are equivalent iff for each input string
x , δ(p,x) is an accepting state iff δ(q,x) is an accepting state. p is
distinguishable from q if there exists an x such that δ(p,x) is in F and v
is not in F or vice versa.
What are the applications of regular expression?
Regular expression in UNIX, Lexical analysis, Pattern searching
Write regular expressions for the following.
(i)Binary numbers that are multiple of 2. (0/1)*.
(ii)Strings of a‟s and b‟s with no consecutive a‟s
.b* (abb*)(a / ε)
(iii) Strings of a‟s and b‟s containing consecutive a‟s.
(a/b)*aa(a/b)*
State Arden’s theorem.
Let P and Q be two regular expressions over ∑. If P does not contain
null string ε over ∑ then R=Q+RP, it has the solution R=QP*
