Automata Theory Questions and Answers Part-4

1. The e-NFA recognizable languages are not closed under :
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned

Answer: d
Explanation: The languages which are recognized by an epsilon Non deterministic automata are closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Negation
e) Star
f) Kleene closure

2. A Language for which no DFA exist is a________
a) Regular Language
b) Non-Regular Language
c) May be Regular
d) Cannot be said

Answer: b
Explanation: A language for which there is no existence of a deterministic finite automata is always Non Regular and methods like Pumping Lemma can be used to prove the same.

3. A DFA cannot be represented in the following format
a) Transition graph
b) Transition Table
c) C code
d) None of the mentioned

Answer: d
Explanation: A DFA can be represented in the following formats: Transition Graph, Transition Table, Transition tree/forest/Any programming Language.

4. When are 2 finite states equivalent?
a) Same number of transitions
b) Same number of states
c) Same number of states as well as transitions
d) Both are final states

Answer: c
Explanation: Two states are said to be equivalent if and only if they have same number of states as well as transitions.

5. Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ∑*
d) Can’t be determined

Answer: b
Explanation: Language to accept a palindrome number or string will be non-regular and thus, its DFA cannot be obtained. Though, PDA is possible.

6. Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches

Answer: d
Explanation: Proper and sequential combination of events leads the machines to work in hand which includes The elevator, Combinational Locks, Traffic Lights, vending machine, etc. Other applications of Finite machine state system are Communication Protocol Design, Artificial Intelligence Research, A Turnstile, etc.

7. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite

Answer: d
Explanation: A language over an alphabet R is a set of strings over A which is uncountable and infinite.

8. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false

Answer: b
Explanation: Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.

9. δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set

Answer: a
Explanation: δ or the Transition function describes the best, how a DFA behaves on a string where to transit next, which direction to take.

10. Which of the following option is correct?
A = {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
c) ε may not belong to A
d) abca ₵ A

Answer: b
Explanation: As the question has dot operation, ε will not be a part of the concatenated set. Had it been a union operation, ε would be a part of the operated set