logo
  • Home
  • Rank
  • Tests
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Contact

Automata Theory Multiple Choice Questions | MCQs | Quiz

Automata Theory Interview Questions and Answers
Practice Automata Theory questions and answers for interviews, campus placements, online tests, aptitude tests, quizzes and competitive exams.

Get Started

•   Finite Automata Introduction
•   Moore Machine
•   Mealy Machine - 1
•   Mealy Machine - 2
•   Finite Automata Definitions
•   DFA Processing Strings
•   Simpler Notations
•   DFA Language
•   Finite Automata
•   Non Deterministic Automata
•   Transition Function
•   NFA Language
•   NFA & DFA Equivalence
•   DFA Applications
•   NFA Applications
•   Epsilon Transition
•   Epsilon Transitions Uses
•   Epsilon Closures
•   Union & Intersection
•   Regular Expression basics
•   Regular Operators
•   Regular Expressions
•   DFA Regular Expressions
•   States Conversion
•   Regular Language - 1
•   Regular Language - 2
•   Expressions-Automata
•   UNIX Regular Expression
•   Lexical Analysis
•   Text Patterns
•   Non Regular Languages
•   Pumping Lemma
•   Lemma Applications
•   Closure Properties
•   Reversal Homomorphism
•   Conversions
•   Emptiness Testing
•   Free Grammar Derivations
•   Inferences & Ambiguity
•   Sentential Forms
•   Parse Tree Construction
•   Trees Inference & Derivation
•   Parsers Applications
•   YACC Parser Generator
•   Markup Languages
•   Ambiguous Grammar
•   State PDA-Acceptance
•   Stack PDA-Acceptance
•   Push Down Automata
•   PDA - Grammars
•   Deterministic PDA
•   Regular Language & DPDA
•   DPDA & Free Languages
•   DPDA & Ambiguous
•   CFG Useless Symbols
•   Epsilon Productions
•   Eliminating Unit Production
•   Chomsky Normal Form
•   Context Free Language
•   CFL-Closure Properties
•   CFL-Other Normal Forms
•   Intersections
•   Transition Diagrams
•   Turing Machine Language-1
•   Turing Machine Language-2
•   Turing Machine & Halting
•   Programming Techniques
•   Multitape Turing Machines
•   One-Tape & Multitape TM's
•   Non Deterministic TM's
•   Multistack Machines
•   Turing Machine Simulation
•   Diagonalization Languages
•   Undecidability
•   Rice's Theorem & PCP
•   Polynomial Time Problems
•   Polynomial Time
•   Hamilton Circuit Problem
•   PSPACE
•   Randomized Algorithm
•   RP & ZPP Complexity

Best Reference Books

Automata Theory Books

« Prev Page
Next Page »

Automata Theory Questions and Answers – Applications of DFA

Posted on May 17, 2017 by Manish

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Applications of DFA”.

1. Given Language: {x | it is divisible by 3}
The total number of final states to be assumed in order to pass the number constituting {0, 1} is
a) 0
b) 1
c) 2
d) 3
View Answer

Answer: c
Explanation: The DFA for the given language can be constructed as follows:
automata-theory-questions-answers-aplications-dfa-q1
advertisement

2. A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011
View Answer

Answer: a
Explanation: If the string is divisible by four, it surely ends with the substring ‘100’ while a binary string divisible by 2 would surely end with the substring ‘10’.

3. Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in Lc.
a) 16
b) 11
c) 5
d) 6
View Answer

Answer: a
Explanation: If L leads to FA1, then for Lc, the FA can be obtained by exchanging the final and non-final states.

4. If L1 and L2 are regular languages, which among the following is an exception?
a) L1 U L2
b) L1 – L2
c) L1 ∩ L2
d) All of the mentioned
View Answer

Answer: d
Explanation: It the closure property of Regular language which lays down the following statement:
If L1, L2 are 2- regular languages, then L1 U L2, L1 ∩ L2, L1C, L1 – L2 are regular language.
advertisement

5. Predict the analogous operation for the given language:
A: {[p, q] | p ϵ A1, q does not belong to A2}
a) A1-A2
b) A2-A1
c) A1.A2
d) A1+A2
View Answer

Answer: a
Explanation: When set operation ‘-‘ is performed between two sets, it points to those values of prior set which belongs to it but not to the latter set analogous to basic subtraction operation.

6. Which among the following NFA’s is correct corresponding to the given Language?
L= {xϵ {0, 1} | 3rd bit from right is 0}
a) automata-theory-questions-answers-aplications-dfa-q6a
b) automata-theory-questions-answers-aplications-dfa-q6b
c) automata-theory-questions-answers-aplications-dfa-q6c
d) None of the mentioned
View Answer

Answer: a
Explanation: The NFA accepts all binary strings such that the third bit from right end is 1 and if not, is send to Dumping state. Note: It is assumed that the input is given from the right end bit by bit.

7. Statement 1: NFA computes the string along parallel paths.
Statement 2: An input can be accepted at more than one place in an NFA.
Which among the following options are most appropriate?
a) Statement 1 is true while 2 is not
b) Statement 1 is false while is not
c) Statement 1 and 2, both are true
d) Statement 1 and 2, both are false
View Answer

Answer: c
Explanation: While the machine runs on some input string, if it has the choice to split, it goes in all possible way and each one is different copy of the machine. The machine takes subsequent choice to split further giving rise to more copies of the machine getting each copy run parallel. If any one copy of the machine accepts the strings, then NFA accepts, otherwise it rejects.
advertisement

8. Which of the following options is correct for the given statement?
Statement: If K is the number of states in NFA, the DFA simulating the same language would have states less than 2k.
a) True
b) False
View Answer

Answer: a
Explanation: If K is the number of states in NFA, the DFA simulating the same language would have states equal to or less than 2k.

9. Let N (Q, ∑, δ, q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, ∑, δ’, q0’, A’), which among the following is true?
a) Q’ = P(Q)
b) Δ’ = δ’ (R, a) = {q ϵ Q | q ϵ δ (r, a), for some r ϵ R}
c) Q’={q0}
d) All of the mentioned
View Answer

Answer: d
Explanation: All the optioned mentioned are the instruction formats of how to convert a NFA to a DFA.

10. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?
a) 226
b) 224
c) 225
d) 223
View Answer

Answer: a
Explanation: The maximum number of states an equivalent DFA can comprise for its respective NFA with k states will be 2k.

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

« Prev Page - Automata Theory Questions and Answers – Equivalence of NFA and DFA
» Next Page - Automata Theory Questions and Answers – Finite Automata with Epsilon Transition

« Automata Theory Questions and Answers – Equivalence of NFA and DFA
Automata Theory Questions and Answers – Finite Automata with Epsilon Transition »
advertisement

Deep Dive @ Sanfoundry:

  1. Ruby Programming Questions and Answers
  2. C++ Programming Examples on Set & String Problems & Algorithms
  3. Compilers Questions and Answers
  4. C Programming Examples on Set & String Problems & Algorithms
  5. Network Theory Questions and Answers
  6. Electromagnetic Theory Questions and Answers
  7. Automata Theory Questions and Answers
  8. Automata Theory Questions and Answers – From Grammars to Push Down Automata
  9. Automata Theory Questions and Answers – Extended Transition Function
  10. Automata Theory Questions and Answers – Finite Automata-Introduction
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below:
LinkedIn | Facebook | Twitter | Google+

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.