Automata Theory Questions and Answers – Deterministic Finite Automata-Introduction and Definition

This set of Automata Theory Interview Questions and Answers focuses on “Deterministic Finite Automata-Introduction and Definition”.

1. Which of the following not an example Bounded Information?
a) fan switch outputs {on, off}
b) electricity meter reading
c) colour of the traffic light at the moment
d) none of the mentioned
View Answer

Answer: b
Explanation: Bounded information refers to one whose output is limited and it cannot be said what were the recorded outputs previously until memorized.

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
View Answer

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
View Answer

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

4. What the following DFA accepts?
Strings such that it ends with ‘101’ accepted by DFA
a) x is a string such that it ends with ‘101’
b) x is a string such that it ends with ‘01’
c) x is a string such that it has odd 1’s and even 0’s
d) x is a strings such that it has starting and ending character as 1
View Answer

Answer: a
Explanation: Strings such as {1101,101,10101} are being accepted while {1001,11001} are not. Thus, this conclusion leads to option a.

5. 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
View Answer

Answer: c
Explanation: Two states are said to be equivalent if and only if they have same number of states as well as transitions.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. What does the following figure most correctly represents?
The figure represents the initial as well as the final state with an iteration of x
a) Final state with loop x
b) Transitional state with loop x
c) Initial state as well as final state with loop x
d) Insufficient Data
View Answer

Answer: c
Explanation: The figure represents the initial as well as the final state with an iteration of x.

7. Which of the following will not be accepted by the following DFA?
ababaabaa is not accepted by DFA
a) ababaabaa
b) abbbaa
c) abbbaabb
d) abbaabbaa
View Answer

Answer: a
Explanation: All the Strings are getting accepted except ‘ababaabaa’ as it is directed to dumping state. Dumping state also refers to the reject state of the automata.
advertisement

8. Which of the following will the given DFA won’t accept?
Epsilon is acceptance state which DFA won’t accept
a) ε
b) 11010
c) 10001010
d) String of letter count 11
View Answer

Answer: a
Explanation: As the initial state is not made an acceptance state, thus ε will not be accepted by the given DFA. For the automata to accept ε as an entity, one should make the initial state as also the final state.

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

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.
advertisement

10. 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
View Answer

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.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.