Automata Theory Multiple Choice Questions on “Regular Language & Expression”.
1. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited
Answer:b
Clarification: States, input symbols,initial state,accepting state and transition function.
2. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
Answer:d
Clarification: Inputs are state and input string output is states.
3. Number of states require to accept string ends with 10.
a) 3
b) 2
c) 1
d) can’t be represented.
Answer:a
Clarification: This is minimal finite automata.
4. Extended transition function is .
a) Q * Σ* -> Q
b) Q * Σ -> Q
c) Q* * Σ* -> Σ
d) Q * Σ -> Σ
Answer:a
Clarification: This takes single state and string of input to produce a state.
5. δ*(q,ya) is equivalent to .
a) δ((q,y),a)
b) δ(δ*(q,y),a)
c) δ(q,ya)
d) independent from δ notation
Answer:b
Clarification: First it parse y string after that it parse a.
6. String X is accepted by finite automata if .
a) δ*(q,x) E A
b) δ(q,x) E A
c) δ*(Q0,x) E A
d) δ(Q0,x) E A
Answer:c
Clarification: If automata starts with starting state and after finite moves if reaches to final step then it called accepted.
7. Languages of a automata is
a) If it is accepted by automata
b) If it halts
c) If automata touch final state in its life time
d) All language are language of automata
Answer:a
Clarification: If a string accepted by automata it is called language of automata.
8. Language of finite automata is.
a) Type 0
b) Type 1
c) Type 2
d) Type 3
Answer:d
Clarification: According to Chomsky classification.
9. Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned
Answer:b
Clarification: Finite automata doesn’t require any stack operation .
10. Number of final state require to accept Φ in minimal finite automata.
a) 1
b) 2
c) 3
d) None of the mentioned
Answer:d
Clarification: No final state requires.
11. Regular expression for all strings starts with ab and ends with bba is.
a) aba*b*bba
b) ab(ab)*bba
c) ab(a+b)*bba
d) All of the mentioned
Answer:c
Clarification: Starts with ab then any number of a or b and ends with bba.
12. How many DFA’s exits with two states over input alphabet {0,1} ?
a) 16
b) 26
c) 32
d) 64
Answer:d
Clarification: Number of DFA’s = 2n * n(2*n).
13. The basic limitation of finite automata is that
a) It can’t remember arbitrary large amount of information.
b) It sometimes recognize grammar that are not regular.
c) It sometimes fails to recognize regular grammar.
d) All of the mentioned
Answer:a
Clarification:Because there is no memory associated with automata.
14. Number of states require to simulate a computer with memory capable of storing ‘3’ words each of length ‘8’.
a) 3 * 28
b) 2(3*8)
c) 2(3+8)
d) None of the mentioned
Answer:b
Clarification: 2(m*n) states requires .
15. FSM with output capability can be used to add two given integer in binary representation. This is
a) True
b) False
c) May be true
d) None of the mentioned
Answer:a
Clarification: Use them as a flip flop output .