logo
  • Home
  • Test & Rank
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Mining
  • Marine
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Jobs
  • 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 – Properties-Non Regular Languages

Posted on May 17, 2017 by Manish

This set of Automata Theory Multiple Choice Questions & Answers focuses on “Properties-Non Regular Languages”.

1. All the regular languages can have one or more of the following descriptions:
i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
Which of the following are correct?
a) i, ii, iv
b) i, ii, iii
c) i, iv
d) i, ii, iii, iv
View Answer

Answer: d
Explanation: The class of languages known as the regular language has atleast four different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
advertisement

2. Which of the technique can be used to prove that a language is non regular?
a) Ardens theorem
b) Pumping Lemma
c) Ogden’s Lemma
d) None of the mentioned
View Answer

Answer: b
Explanation: We use the powerful technique called Pumping Lemma, for showing certain languages not to be regular. We use Ardens theorem to find out a regular expression out of a finite automaton.

3. Which of the following language regular?
a) {aibi|i>=0}
b) {aibi|0<i<5}
c) {aibi|i>=1}
d) None of the mentioned
View Answer

Answer: b
Explanation: Here, i has limits i.e. the language is finite, contains few elements and can be graphed using a deterministic finite automata. Thus, it is regular. Others can be proved non regular using Pumping lemma.

4. Which of the following are non regular?
a) The set of strings in {a,b}* with an even number of b’s
b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a
c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0.
d) None of the mentioned
View Answer

Answer: d
Explanation: All of the given languages are regular and finite and thus, can be represented using respective deterministic finite automata. We can also use mealy or moore machine to represent remainders for option c.
advertisement

5. If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned
View Answer

Answer: b
Explanation: This is a simple example of a closure property: a property saying that the set of DFA-regular languages is closed under certain operations.

6. Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes.
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.
c) A language L is NFA-regular if and only if it is DFA-regular.
d) None of the mentioned
View Answer

Answer: b
Explanation: Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.

7. Myphill Nerode does the following:
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Both (a) and (b)
d) None of the mentioned
View Answer

Answer: c
Explanation: In automata theory, the Myphill Nerode theorem provides a necessary and sufficient condition for a language to be regular. The Myphill Nerode theorem can be used to show a language L is regular by proving that the number of equivalence classes of RL(relation) is finite.
advertisement

8. Which of the following are related to tree automaton?
a) Myphill Nerode Theorem
b) State machine
c) Courcelle’s Theorem
d) All of the mentioned
View Answer

Answer: d
Explanation: The myphill nerode theorem can be generalized to trees and an application of tree automata prove an algorithmic meta theorem about graphs.

9. Given languages:
i) {anbn|n>=0}
ii) <div>n</div>n
iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences
Which of the following is/are non regular?
a) i, iii
b) i
c) iii
d) i, ii, iii
View Answer

Answer: d
Explanation: There is no regular expression that can parse HTML documents. Other options are also non-regular as they cannot be drawn into finite automaton.

10. Finite state machine are not able to recognize Palindromes because:
a) Finite automata cannot deterministically find the midpoint
b) Finite automata cannot remember arbitarily large amount of data
c) Even if the mid point is known, it cannot find whether the second half matches the first
d) All of the mentioned
View Answer

Answer: d
Explanation: It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.

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 – Finding Patterns in Text,Algebric Laws and Derivatives
» Next Page - Automata Theory Questions and Answers – Pumping Lemma for Regular Language

« Automata Theory Questions and Answers – Finding Patterns in Text,Algebric Laws and Derivatives
Automata Theory Questions and Answers – Pumping Lemma for Regular Language »
advertisement

Deep Dive @ Sanfoundry:

  1. C Programming Examples on Set & String Problems & Algorithms
  2. PHP Questions and Answers
  3. Discrete Mathematics Questions and Answers
  4. Electromagnetic Theory Questions and Answers
  5. Compilers Questions and Answers
  6. Network Theory Questions and Answers
  7. Automata Theory Questions and Answers
  8. Automata Theory Questions and Answers – Pumping Lemma for Regular Language
  9. Theory of Computation – Regular Expressions and Regular Languages
  10. Automata Theory Questions and Answers – CFL- Closure Properties/Decision Properties
Manish Bhojasia
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & 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, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Facebook | Twitter

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.