Automata Theory Multiple Choice Questions | MCQs | Quiz

1. Finite state machine is ___________tuple machine.

a) 4

b) 5

c) 6

d) unlimited

View Answer: 5

2. Transition function of DFA machine maps.

a) Σ x Q -> Σ

b) Q x Q -> Σ

c) Σ x Σ -> Q

d) Q x Σ -> Q

View Answer: Q x Σ -> Q

3. Number of states require to accept string ends with 101.

a) 3

b) 4

c) 2

d) can’t be represented.

View Answer: 4

4. Language of finite automata is generated by

a) Type 0 grammar

b) Type 1 grammar

c) Type 2 grammar

d) Type 3 grammar

View Answer: Type 3 grammar

5. Finite automata needs minimum _______ number of stacks.

a) 0

b) 1

c) 2

d) None of the mentioned

View Answer: 0

6. Φ in minimal finite automata need _____________ no. of final states

a) 1

b) 2

c) 3

d) None of the mentioned

View Answer: None of the mentioned

7. Regular expression for all strings starts with ab and ends with ba is.

a) aba*b*ba

b) ab(ab)*ba

c) ab (a+b)*ba

d) All of the mentioned

View Answer: ab (a+b)*ba

8.Which of the following are the examples of finite state machine system?

a) Control Mechanism of an elevator, Traffic Lights

b) Combinational Locks

c) Digital Watches

d) Both a & b

View Answer: Both a & b

9.Two finite states are equivalent if ?

a) Both are final states

b) Both are non-final states

c) both have same number of states as well as transitions

d) Both a & b

View Answer: Both a & b

10.The finite automata  is called NFA when there exists____________ for a specific input from current state to next state

a) Single path

b) Multiple paths

c) Only two paths

d) None

View Answer: Multiple paths

11.Transition function of NFA machine is given by.

a) Σ x Q -> Σ

b) Q x Σ -> Σ

c) Q x Σ -> Q

d) Q x Σ -> 2 power Q

View Answer: Q x Σ -> 2 power Q

12.Backtracking is allowed in 

a) NDFA

b) DFA

c) Both a & b

d) None

View Answer: DFA

13.Transition function of ε-NFA machine is given by.

a) Σ x Q -> Σ

b) Q x Σ -> Σ

c) Q x Σ U {ε} -> 2 power Q

d) Q x Σ U {ε} -> Q

View Answer: Q x Σ U {ε} -> 2 power Q

14. ε-closure of state is combination of self state and ________________

a) ε-reachable state

b) initial state

c) Final state

d) All

View Answer: ε-reachable state

15. L={ε, a, aa, aaa, aaaa,……..} is represented by ______________

a) a*

b) a+

c) Both a & b

d) None

View Answer: a*

16. The generators of languages are ________________

a) Regular expression

b) Grammars

c) FSM

d) All

View Answer: Grammars

17.The regular expression of language which is starting and ending with different symbols is __________________

a) a(a+b)*b

b) b(a+b)*a

c) a(a+b)*b + b(a+b)*a

d) All

View Answer: a(a+b)*b + b(a+b)*a

18.Context Free Grammars has ________tuples

a) 5

b) 4

c) 3

d) None

View Answer: 4

19.The trees which represent derivations in a CFG are called ________

a) Parse tree

b) Derivation tree

c) Both a & b

d) None

View Answer: Both a & b

20. A grammar is said to be ambiguous grammar if it ________

a) produces more than one derivation tree

b) produces more than one left most derivation

c) produces more than one right most derivation

d) All

View Answer: All