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 – Sentential Forms

Posted on May 17, 2017 by Manish

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

1. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False
View Answer

Answer: a
Explanation: A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.
advertisement

2. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned
View Answer

Answer: c
Explanation: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.

3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned
View Answer

Answer: d
Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.

4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer

Answer: c
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
advertisement

5. For the given Regular expression, the minimum number of terminals required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6
View Answer

Answer: b
Explanation: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01
6. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a

a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned
View Answer

Answer: b
Explanation: The following format of grammar is of Regular grammar and is a part of Context free grammar i.e. like a specific form whose finite automata can be generated.

7. Which among the following is a CFG for the given Language:
L={x∈{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned
View Answer

Answer: c
Explanation: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.
advertisement

8. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned
View Answer

Answer: a
Explanation: The advantage of using high level programming language like C and Pascal is that they allow us to write statements that look more like English.

9. Which among the following is the correct grammar for the given language?
L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned
View Answer

Answer: c
Explanation: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S

10. L={0i1j2k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010
View Answer

Answer: a
Explanation: It is just required to put the value in the variables in the question and check if it satisfies or not.

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 – The Language of a Grammar, Inferences and Ambiguity
» Next Page - Automata Theory Questions and Answers – Construction and Yield of a Parse Tree

« Best Reference Books – M.Sc. – Microbiology
Best Reference Books – M.Sc. – Applied Geology »
advertisement

Deep Dive @ Sanfoundry:

  1. Ruby Programming Questions and Answers
  2. Javascript Questions and Answers
  3. LISP Questions and Answers
  4. Python Questions and Answers
  5. C Tutorials
  6. Network Theory Questions and Answers
  7. PHP Questions and Answers
  8. Electromagnetic Theory Questions and Answers
  9. Compilers Questions and Answers
  10. Automata Theory Questions and Answers
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.