This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Context Free

Grammar-Derivations and Definitions”.

1. The entity which generate Language is termed as:

a) Automata
b) Tokens
c) Grammar
d) Data
View Answer
Answer: c
Explanation: The entity which accepts a language is termed as Automata while the one which generates it
is called Grammar. Tokens are the smallest individual unit of a program.
2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
View Answer
Answer: c
Explanation: Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has
the production rule where the production is context dependent i.e. aAb->agb.
3. Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
View Answer
Answer: d
Explanation: Every regular language can be produced by context free grammar and context free
language can be produced by context sensitive grammar and so on.

4. The Grammar can be defined as: G=(V, ∑, p, S)

In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
View Answer
Answer: b
Explanation: G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S=
Starting Variable.
5. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
View Answer
Answer: d
Explanation: There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is
possible to make a dfa or nfa representing the language set.
6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
View Answer
Answer: c
Explanation: According to the definition, the starting variable can produce another variable or any terminal
or a variable which leads to terminal.
7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
View Answer
Answer: d
Explanation: L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are
correct implying none of them to be wrong.
advertisement

8. The minimum number of productions required to produce a language consisting of palindrome strings
over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
View Answer
Answer: c
Explanation: The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
View Answer
Answer: a
Explanation: Regular grammar is a subset of context free grammar and thus all regular grammars are
context free.
10. Are ambiguous grammar context free?
a) Yes
b) No
View Answer
Answer: a
Explanation: A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or
more distinct leftmost derivations.

Automata Theory Questions and Answers – The Language of a Grammar, Inferences and Ambiguity

This set of Automata Theory Problems focuses on “The Language of a Grammar, Inferences and
Ambiguity”.

1. Which of the following is not a notion of Context free grammars?

a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
View Answer
Answer: d
Explanation: The following are the notions to express Context free grammars:
a) Recursive Inferences
b) Derivations
c) Sentential form
d) Parse trees
2. State true or false:
Statement: The recursive inference procedure determines that string w is in the language of the variable
A, A being the starting variable.
a) true
b) false
View Answer
Answer: a
Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain
variable.
3. Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Both Recursive Inference and Derivations
d) None of the mentioned
View Answer
Answer: c
Explanation: Two inference approaches:
1. Recursive inference, using productions from body to head
2. Derivations, using productions from head to body
4. If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w.
w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
View Answer
Answer: d
Explanation: Parse trees are an alternative representation to derivations and recursive inferences. There
can be several parse trees for the same string.
5. Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
View Answer
Answer: a
Explanation: Yes, they are equivalent. Both the terminologies represent the two approaches of recursive
inferencing.
6. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
View Answer
Answer: b
Explanation: A->aA=>aaA=>aab
7. An expression is mentioned as follows. Figure out number of incorrect notations or symbols, such that
a change in those could make the expression correct.
L(G)={w in T*|S→*w}
a) 0 Errors
b) 1 Error
c) 2 Error
d) Invalid Expression
View Answer
Answer: a
Explanation: For the given expression, L(G)={w in T*|S→*w}, If G(V, T, P, S) is a CFG, the language of G,
denoted by L(G), is the set of terminal strings that have derivations from the start symbol.
8. The language accepted by Push down Automaton:
a) Recursive Language
b) Context free language
c) Linearly Bounded language
d) All of the mentioned
View Answer
Answer: b
Explanation: Push down automata accepts context free language.
9. Which among the following is the correct option for the given grammar?
G->X111|G1,X->X0|00
a) {0a1b|a=2,b=3}
b) {0a1b|a=1,b=5}
c) {0a1b|a=b}
d) More than one of the mentioned is correct
View Answer
Answer: a
Explanation: Using the recursive approach, we can conclude that option a is the correct answer, and its
not possible for a grammar to have more than one language.
10. Which of the following the given language belongs to?
L={ambmcm| m>=1}
a) Context free language
b) Regular language
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: d
Explanation: The given language is neither accepted by a finite automata or a push down automata.
Thus, it is neither a context free language nor a regular language.
11. Choose the correct option:
Statement: There exists two inference approaches:
a) Recursive Inference
b) Derivation

a) true
b) partially true
c) false
d) none of the mentioned
View Answer
Answer: a
Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain
variable.
advertisement

12. Choose the correct option:

Statement 1: Recursive Inference, using productions from head to body.
Statement 2: Derivations, using productions from body to head.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 and Statement 2, both are false
c) Statement 1 is true and Statement 2 is false
d) Statement 2 is true and Statement 1 is true
View Answer
Answer: b
Explanation: Both the statements are false. Recursive Inference, using productions from body to head.
Derivations, using productions from head to body.
13. Which of the following statements are correct for a concept called inherent ambiguity in CFL?
a) Every CFG for L is ambiguous
b) Every CFG for L is unambiguous
c) Every CFG is also regular
d) None of the mentioned
View Answer
Answer: a
Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.
14. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned
View Answer
Answer: a
Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can
only have ambiguous grammars.

Automata Theory Questions and Answers – Sentential Forms

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

Automata Theory Questions and Answers – Construction and Yield of a Parse Tree

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Construction and
Yield of a Parse Tree”.

1. The most suitable data structure used to represent the derivations in compiler:
a) Queue
b) Linked List
c) Tree
d) Hash Tables
View Answer
Answer: c
Explanation: The tree, known as “Parse tree” when used in a compiler, is the data structure of choice to
represent the source program.
2. Which of the following statement is false in context of tree terminology?
a) Root with no children is called a leaf
b) A node can have three children
c) Root has no parent
d) Trees are collection of nodes, with a parent child relationship
View Answer
Answer: a
Explanation: A node has atmost one parent, drawn above the node, and zero or more children drawn
below. Lines connect parents to children. There is one node, one root, that has no parent; this node
appears to be at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves
are called interior nodes.
3. In which order are the children of any node ordered?
a) From the left
b) From the right
c) Arbitrarily
d) None of the mentioned
View Answer
Answer: a
Explanation: The children of a node are ordered from the left and drawn so. If N is to the left of node M,
then all the descendents of N are considered to be to the left of all the descendents of M.
4. Which among the following is the root of the parse tree?
a) Production P
b) Terminal T
c) Variable V
d) Starting Variable S
View Answer
Answer: d
Explanation: The root is labelled by the start symbol. All the leaves are either labelled by a a terminal or
with e.
5. For the expression E*(E) where * and brackets are the operation, number of nodes in the respective
parse tree are:
a) 6
b) 7
c) 5
d) 2
View Answer
Answer: b

Explanation:
6. The number of leaves in a parse tree with expression E*(E) where * and () are operators
a) 5
b) 2
c) 4
d) 3
View Answer
Answer: a

Explanation:
7. Which of the following does the given parse tree correspond to?

a) P->1100
b) P->0110
c) P->1100ε
d) P->0101
View Answer
Answer: b
Explanation: The following is a parse tree for the production 0110 over {0,1}*.
advertisement

8. A grammar with more than one parse tree is called:

a) Unambiguous
b) Ambiguous
c) Regular
d) None of the mentioned
View Answer
Answer: b
Explanation: A context free grammar G is ambiguous if there is at least one string in L(G) having two or
more distinct derivation trees or equivalently, two or more distinct leftmost derivations.
9. __________ is the acyclic graphical representation of a grammar.
a) Binary tree
b) Oct tree
c) Parse tree
d) None of the mentioned
View Answer
Answer: c
Explanation: In order to graphically represent a derivation of a grammar we need to use parse trees.
10. Grammar is checked by which component of compiler
a) Scanner
b) Parser
c) Semantic Analyzer
d) None of the mentioned
View Answer
Answer: Parser or syntax analyzer is the one responsible for checking the grammar and reporting errors.
In this phase, parse tree is generated and syntax is analyzed.

Automata Theory Questions and Answers – Inferences to Trees, Trees to Derivations

This set of Automata Theory Question Bank focuses on “Inferences to Trees, Trees to Derivations”.

1. A symbol X is ________ if there exists : S->* aXb

a) reachable
b) generating
c) context free
d) none of the mentioned
View Answer
Answer: a
Explanation: A symbol X is generating if there exists : X->*w for some w that belongs to T*.
Also, a symbol can never be context free.
2. A symbol X is called to be useful if and only if its is:
a) generating
b) reachable
c) both generating and reachable
d) none of the mentioned
View Answer
Answer: c
Explanation: For a symbol X to be useful, it has to be both reachable and generating i.e.
S->* aXb -> * w where w belongs to T*.
3. Which of the following is false for a grammar G in Chomsky Normal Form:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) None of the mentioned
View Answer
Answer: d
Explanation: G, a CFG is said to be in Chomsky normal form if all its productions are in one of the
following form:
A->BC or A->a
4. Given Checklist:
a) G has no useless symbols
b) G has no unit productions
c) G has no epsilon productions
d) Normal form for production is violated
Is it possible for the grammar G to be in CNF with the following checklisy ?
a) Yes
b) No
View Answer
Answer: b
Explanation: The grammar is not in CNF if it violates the normal form of the productions which is strictly
restricted.
5. State true or false:
Statement: A CNF parse tree’s string yield (w) can no longer be 2h-1.
a) true
b) false
View Answer
Answer: a
Explanation: It is the parse tree theorem which states:
Given: Suppose we have a parse tree for a string w, according to a CNF grammar, G=(V, T, P, S). Let h
be the height of the parse tree. Now, Implication: |w|<=2h-1.
6. If |w|>=2h, then its parse tree’s height is at least _____
a) h
b) h+1
c) h-1
d) 2h
View Answer
Answer: b
Explanation: It is the basic implication of Parse tree theorem (assuming CNF). If the height of the parse
tree is h, then |w| <=2h-1.
7. If w belongs to L(G), for some CFG, then w has a parse tree, which tell us the ________ structure of w.
a) semantic
b) syntactic
c) lexical
d) all of the mentioned
View Answer
Answer: b
Explanation: A parse tree or concrete syntactic tree is an ordered, rooted tree that represents the
syntactic structure of a string according to some context free grammar.
advertisement

8. Which of the following are distinct to parse trees?

a) abstract parse trees
b) sentence diagrams
c) both abstract parse trees and sentence diagrams
d) none of the mentioned
View Answer
Answer: c
Explanation: Both of the mentioned are different from parse trees. Sentence diagrams are pictorial
representations of grammatical structure of a sentence.
9. Choose the correct option:
Statement: Unambiguity is the ideal structure of a language.
a) true
b) partially true
c) false
d) cant be said
View Answer
Answer: a
Explanation: Ideally, there should be only one parse tree for each string, i.e. the language should be
unambiguous.
10. Is the given statement correct?
Statement: The mere existence of several derivations is not an issue, its is the existence of several parse
trees that ruins a grammar.
a) Yes
b) No
View Answer
Answer: a
Explanation: It is also true that multiple leftmost or rightmost derivations do cause ambiguity.
Unfortunately, it is not possible to remove the ambiguity always.

Automata Theory Questions and Answers – Applications – Parsers

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

1. To derive a string using the production rules of a given grammar, we use:

a) Scanning
b) Parsing
c) Derivation
d) All of the mentioned
View Answer
Answer: b
Explanation: Parsing is required to check the acceptability of a string. Further, comes the syntactical
phase which is taken care by other phases of compiler.
2. Which of the following parser reaches the root symbol of the tree at last?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
View Answer
Answer: b
Explanation: Bottom up parser starts from the bottom with the string and comes up to the start
symbolusing a parse tree or a derivation tree.
3. Left corner parsing methof uses which of the following?
a) Top down parser
b) Bottom up parser
c) TOP down and Bottom up parser
d) None of the mentioned
View Answer
Answer: c
Explanation: It is a hybrid method which works bottom up along the left edges of each subtree, and top
down on the rest of the parse tree.
4. Which of the following parser performs top down parsing?
a) LALR parser
b) LL parser
c) Recursive Accent parser
d) None of the mentioned
View Answer
Answer: b
Explanation: Bottom up parsing is done by shift reduce parsers like LALR parsers, Operator precedence
parsers, simple precedence parsers, etc.
5. Which of the following is true for shift reduce parsers?
a) Scans and parses the input in one forward pass over the text, without any backup.
b) A shift command advances in the input stream by one symbol
c) LALR parser
d) All of the mentioned
View Answer
Answer: d
Explanation: The mentioned are the correct and proper functions of a shift reduce parsers. The parsing
methods are most commonly used for parsing programming languages, etc.
6. State true or false:
Statement: LALR parsers uses tables rather than mutually recursive functions.
a) true
b) false
View Answer
Answer: b
Explanation: It is exactly the opposite case where LALR parsers uses mutually recursive functions instead
of tables. It is a simplified version of canonical left to right parser.
7. LALR in LALR parser stands for:
a) Left aligned left right parser
b) Look ahead left to right parser
c) Language Argument left to right parser
d) None of the mentioned
View Answer
Answer:
Explanation: LALR stands for Look ahead left to right parsers. It has more language recognition power
than LR(0) parser.
advertisement

8. Which of the following can be a LALR parser generator?

a) YACC
b) GNU Bison
c) YACC and GNU Bison
d) None of the mentioned
View Answer
Answer: c
Explanation: YACC is a computer code for UNIX operating system which generates a LALR parser. On
the other hand GNU Bison or Bison can generate LALR and GLR parsers.
9. Which of the following parsers do not relate to Bottom up parsing?
a) LL parser
b) Recursive descent parser
c) Earley parsers
d) All of the mentioned
View Answer
Answer: d
Explanation: All the following mentioned are top down parsers and begin their operation from the starting
symbol.
10. Which of the following is true for a predictive parser?
a) Recursive Descent parser
b) no backtracking
c) Recursive Descent parser and no backtracking
d) None of the mentioned
View Answer
Answer: c
Explanation: Predictive parsing is possible only for the class of LL-grammars, which are the CFG for
which there exists some positive integer k that allows a recursive descent parser to decide which
production to use by examining only the next k tokens of input.

Automata Theory Questions and Answers – YACC Parser Generator

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “YACC Parser
Generator”.

1. YACC is a computer program for ______ operation system.

a) Windows
b) DOS
c) Unix
d) openSUSE
View Answer
Answer: c
Explanation: YACC technique is a computer code for the Unix operating system. It is a LALR parser
generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source
code.
2. YACC is an acronym for:
a) Yes Another Compile Compiler
b) Yet Another Compile Compiler
c) Yet Another Compiler Compiler
d) Yes Another Compiler Compiler
View Answer
Answer: c
Explanation: YACC stands for ‘Yet another compiler compiler’ and it was developed by Stephen Johnson
in B programming language later translated to C.
3. The YACC takes C code as input and outputs_________
a) Top down parsers
b) Bottom up parsers
c) Machine code
d) None of the mentioned
View Answer
Answer: b
Explanation: The YACC takes C code as input and produces shift reduce parsers in C,also known as
Bottom up parsers which execute C snippets with the associated rule.
4. The _______ table is created by YACC.
a) LALR parsing
b) LL parsing
c) GLR parsing
d) None of the mentioned
View Answer
Answer: a
Explanation: LALR parser generator is software tool that reads a BNF grammar and creates a LALR
parser which is capable of parsing files written in programming language identified by BNF grammar.
5. The original YACC as written in __________ language
a) R programming language
b) C programming language
c) B programming language
d) None of the mentioned
View Answer
Answer: c
Explanation: Stephen Johnson wrote this parser generator in B programming language which was further
modified and written in C, JAVA, Python, etc.
6. Which of the following is false for B programming language?
a) Typeless
b) Influenced by PL/I
c) Designed by Dennis Ritchie
d) None of the mentioned
View Answer
Answer: d
Explanation: B was programming language designed by Dennis Ritchie and Ken Thompson for recursive,
non numeric, system and language softwares. It was a typeless language, everything is a word.
7. Which of the following is false for BNF?
a) BNF means Backus Naur Form
b) It is a normal form used in Data base normalization
c) It is a notation technique for context free grammar
d) None of the mentioned
View Answer
Answer: b
Explanation: The normal form used in Data base normalization is BCNF i.e. Boyce Codd normal form and
NOT Backus Naur Form.
advertisement

8. State true or false:

Statement: BNF is a metasyntax used to express CFG
a) True
b) False
View Answer
Answer: a
Explanation: BNF is a metasyntax used to express context free grammar, moreover a formal way to
express the language.
9. Which of the following are not used to express CFG?
a) BNF
b) EBNF, ABNF
c) Van Wijngaarden form
d) None of the mentioned
View Answer
Answer: d
Explanation: W grammar or van Wijngaarden form is used to define potentially infinite context free
grammars in a finite number of rules. It is an example of larger class of affix grammars. This technique
was used to define the P/L Algol 68.
10. Which of the following version of Unix came up with YACC first?
a) V3
b) V5
c) CB UNIX
d) Unix-RT
View Answer
Answer: a
Explanation: Yacc appeared in version 3 of unix, though full description was published by 1975.

Automata Theory Questions and Answers – Markup Languages

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

1. XML is a _________ markup language.

a) meta
b) beta
c) octa
d) peta
View Answer
Answer: a
Explanation: Generally speaking, a meta language is a language used to describe a language. XML is a
metalanguage that is used to describe a markup language.
2. XML uses _________ principle to formally describe the data.
a) DDL
b) DTD
c) DML
d) None of the mentioned
View Answer
Answer: b
Explanation: A document type definition (DTD) is a set of markup declarations that define a document
type for an SGML-family markup language (SGML, XML, HTML). A Document Type Definition (DTD)
defines the legal building blocks of an XML document. It defines the document structure with a list of legal
elements and attributes.
3. Which among the following are true for an Extensible markup language?
a) Human Readable/ Machine Readable
b) Extended from SGML
c) Developed by www consortium
d) All of the mentioned
View Answer
Answer: d
Explanation: XML is an open format markup language with a filename extension of .xml.
4. Which of them have XML as their default format?
a) IWork
b) LibreOffice
c) OpenOffice
d) All of the mentioned
View Answer
Answer: d
Explanation: More that hundred of document formats using XML syntax have been developed, including
RSS, Atom, SOAP and XHTML.
5. A DTD is associated with a XML file by means of ___________
a) Function
b) <!DOCTYPE>
c) Macros
d) None of the mentioned
View Answer
Answer: b
Explanation: A document type definition defines the legal building blocks of an XML document .
6. Which of the following is not an example of electronic mark up?
a) HTML
b) LaTeX
c) PostScript
d) None of the mentioned
View Answer
Answer: d
Explanation: There are three categories of electronic markup: presentational, procedural, and descriptive
markup. Examples are XML, HTML, LaTeX, etc.
7. troff and nroff are _________ in Unix.
a) functions
b) typesetting tools
c) System sofwares
d) None of the mentioned
View Answer
Answer: b
Explanation: Early examples of computer markup languages can be found in typesetting tools like troff
and nroff in Unix.
advertisement

8. SGML stands for:

a) Standard Generalized Markup Language
b) Standardized General Markup Language
c) Standard General Markup Language
d) Standard Generalized Markdown Language
View Answer
Answer: a
Explanation: SGML is an acronym for Standard Generalized Markup Language.
9. Markup Languages are not used for which of the following?
a) playlists
b) content syndication
c) user interfaces
d) none of the mentioned
View Answer
Answer: d
Explanation: Markup languages originated with text documents, but there is an increasing use of mark up
language in presentation of other types of information, including playlists, vector graphics, user interfaces
and web services.
10. Which of the following is incorrect for HTML5 markup construct?
a) Start tags: <section>
b) End tags: </section>
c) <img src= “abc.jpeg” >ABC</img>
d) None of the mentioned
View Answer
Answer: d
Explanation: All the mentioned options are valid HTML5 arguments and executes properly.

Automata Theory Questions and Answers – Ambiguous Grammar

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

1. A CFG is ambiguous if
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned
View Answer
Answer: b
Explanation: A context free grammar is ambiguous if it has more than one parse tree generated or more
than one leftmost derivations. An unambiguous grammar is a context free grammar for which every valid
string has a unique leftmost derivation.
2. Which of the following are always unambiguous?
a) Deterministic Context free grammars
b) Non-Deterministic Regular grammars
c) Context sensitive grammar
d) None of the mentioned
View Answer
Answer: a
Explanation: Deterministic CFGs are always unambiguous , and are an important subclass of
unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.
3. A CFG is not closed under
a) Dot operation
b) Union Operation
c) Concatenation
d) Iteration
View Answer
Answer: d
Explanation: The closure property of a context free grammar does not include iteration or kleene or star
operation.
4. Which of the following is an real-world programming language ambiguity?
a) dangling else problem
b) halting problem
c) maze problem
d) none of the mentioned
View Answer
Answer: a
Explanation: Dangling else problem: In many languages,the else in an if-then-else statement is optional,
which results into nested conditionals being ambiguous, at least in terms of the CFG.
5. Which of the following is a parser for an ambiguous grammar?
a) GLR parser
b) Chart parser
c) All of the mentioned
d) None of the mentioned
View Answer
Answer: c
Explanation: GLR parser: a type of parser for non deterministic and ambiguous grammar
Chart parser: aa type of parser for ambiguous grammar.
6. A language that admits only ambiguous grammar:
a) Inherent Ambiguous language
b) Inherent Unambiguous language
c) Context free language
d) Context Sensitive language
View Answer
Answer: a
Explanation: A context free language for which no unambiguous grammar exists, is called Inherent
ambiguous language.
7. Which of the following is an example of inherent ambiguous language?
a) {an|n>1}
b) {anbncmdm| n,m > 0}
c) {0n1n|n>0}
d) None of the mentioned
View Answer
Answer: b
Explanation: This set is context-free, since the union of two context-free languages is always context free.
advertisement

8. State true or false:

Statement: R->R|T T->ε is an ambiguous grammar
a) true
b) false
View Answer
Answer: a
Explanation: The production can be either itself or an empty string. Thus the empty string has more than
one leftmost derivations, depending on how many times R->R is being used.
9. In context to ambiguity, the number of times the following programming statement can be interpreted
as:
Statement: if R then if T then P else V
a) 2
b) 3
c) 4
d) 1
View Answer
Answer: a
Explanation: Dangling else problem
if R then (if T then P else V) and if R then (if T then P) else V are the two ways in which the given if else
statement can be parsed.
10. CFGs can be parsed in polynomial time using__________
a) LR parser
b) CYK algorithm
c) SLR parser
d) None of the mentioned
View Answer
Answer: CYK algorithm parses the CFG in polynomial time while LR parsers do the same in linear time.
DCFGs are accepted by DPDAs and parsed using LR parsers or CYK algorithm.

Automata Theory Questions and Answers – CFG-Eliminating Useless Symbols

This set of Automata Theory Assessment Questions and Answers focuses on “CFG-Eliminating Useless
Symbols”.

1. Suppose A->xBz and B->y, then the simplified grammar would be:
a) A->xyz
b) A->xBz|xyz
c) A->xBz|B|y
d) none of the mentioned
View Answer
Answer: a
Explanation: For the first step, substitute B in first production as it only produces terminal and remove B
production as it has already been utilized.
We get A->xBz|xyz and now, as B has no production, we eliminate the terms which hold the variable B,
thus the answer remain A->xyz.
2. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?
a) S->A
b) A->aA
c) A->e
d) B->bA
View Answer
Answer: d
Explanation: Some derivations are not reachable from the starting variable. As B is not reachable from
the starting variable, it is a useless symbol and thus, can be eliminated.
3. Given:
S->…->xAy->…->w
if ____________, then A is useful, else useless symbol.
a) A is a non terminal
b) A is a terminal
c) w Î L
d) w Ë L
View Answer
Answer: c
Explanation: Whatever operation we perform in intermediate stages, if the string produced belongs to the
language, A is termed as useful and if not, not a useful variable.
4. Given:
S->aSb
S->e
S-> A
A->aA
B->C
C->D
The ratio of number of useless variables to number of useless production is:
a) 1
b) 3/4
c) 2/3
d) 0
View Answer
Answer: a
Explanation: A, B, C, D are the useless symbols in the given grammar as they never tend to lead to a
terminal. The productions S-> A, A->aA, B->C, C->D are also termed as useless production as they will
never produce a string to the grammar.
5. Given grammar G:
S->aS|A|C
A->a
B->aa
C->aCb
Find the set of variables thet can produce strings only with the set of terminals.
a) {C}
b) {A,B}
c) {A,B,S}
d) None of the mentioned
View Answer
Answer: c
Explanation: First step: Make a set of variables that directly end up with a terminal
Second step: Modify the set with variables that produce the elements of above
generated set.
The rest variables are termed as useless.
6. Given grammar:
S->aS|A
A->a
B->aa
Find the number of variables reachable from the Starting Variable?
a) 0
b) 1
c) 2
d) None of the mentioned
View Answer
Answer: b
Explanation: Use a dependency graph to find which variable is reachable and which is not.

7. Inorder to simplify a context free grammar, we can skip the following operation:
a) Removal of null production
b) Removal of useless symbols
c) Removal of unit productions
d) None of the mentioned
View Answer
Answer: d
Explanation: Inorder to simplify the grammar all of the process including the removal of null productions,
unit productions and useless symbols is necessary.
8. Given a Grammar G:
S->aA
A->a
A->B
B->A
B->bb
Which among the following will be the simplified grammar?
a) S->aA|aB, A->a, B->bb
b) S->aA|aB, A->B, B->bb
c) S->aA|aB, A->a, B->A
d) None of the emntioned
View Answer
Answer: a
Explanation: Step 1: Substitute A->B
Step 2: Remove B->B
Step 3: Substitute B->A
Step 4: Remove Repeated productions
9. Simplify the given grammar:
A-> a| aaA| abBc
B-> abba| b

a) A-> a| aaA| ababbAc| abbc

b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned
View Answer
Answer: a
Explanation: Using the substitution rules, we can simply eradicate what is useless and thus produce the
simplified result i.e. A-> a| aaA| ababbAc| abbc.
advertisement

10. In context to the process of removing useless symbols, which of the following is correct?
a) We remove the Nullable variables
b) We eliminate the unit productions
c) We eliminate products which yield no terminals
d) All of the mentioned
View Answer
Answer: c
Explanation: In the process of removal of useless symbols, we want to remove productions that can never
take part in any derivation

Automata Theory Questions and Answers – Eliminating Epsilon Productions

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Eliminating
Epsilon Productions”.

1. The use of variable dependency graph is in:

a) Removal of useless variables
b) Removal of null productions
c) Removal of unit productions
d) None of the mentioned
View Answer
Answer: a
Explanation: We use the concept of dependency graph inorder to check, whether any of the variable is
reachable from the starting variable or not.
2. The variable which produces an epsilon is called:
a) empty variable
b) nullable
c) terminal
d) all of the mentioned
View Answer
Answer: b
Explanation: Any variable A for which the derivation: A->*e is possible is called Nullable.
3. Statement:
For A-> e ,A can be erased. So whenever it appears on the left side of a production, replace with another
production without the A.
State true or false:
a) true
b) false
View Answer
Answer: b
Explanation: A can be erased. So whenever it appears on the right side of the production, replace with
another production without the A.
4. Simplify the given grammar:
S->aXb
X->aXb | e
a) S->aXb | ab, X-> aXb | ab
b) S->X | ab, X-> aXb | ab
c) S->aXb | ab, X-> S | ab
d) None of the mentioned
View Answer
Answer: a
Explanation: As X is nullable, we replace every right hand side presence of X with e and produce the
simplified result.
5. Consider the following grammar:
A->e
B->aAbC
B->bAbA
A->bB
The number of productions added on the removal of the nullable in the given grammar:
a) 3
b) 4
c) 2
d) 0
View Answer
Answer: b
Explanation: The modified grammar aftyer the removal of nullable can be shown as:
B->aAbC| abC
B->bAbA| bbA| bAb| bb
A->bB
6. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar G’
having no e productions.
a) e ∈ L(G)
b) w ∉ L(G)
c) e ∉ L(G)
d) w ∈ L(G)
View Answer
Answer: c
Explanation: Theorem: Let G = (V, T, S, P) be a CFG such that e ∉ L(G). Then there exists an equivalent
grammar G’ having no e-productions.
7. For each production in P of the form:
A-> x1x2x3…xn
put into P’ that production as well as all those generated by replacing null variables with e in all possible
combinations. If all x(i) are nullable,
a) A->e is put into P’
b) A->e is not put into P’
c) e is a member of G’
d) None of the mentioned
View Answer
Answer: b
Explanation: It is an exception that A->e is not put into P’ if all x(i) are nullable variables.
advertisement

8. For the given grammar G:

S->ABaC
A->BC
B->b| e
C->D| e
D-> d
Remove the e productions and generate the number of productions from S in the modified or simplified
grammar.
a) 6
b) 7
c) 5
d) 8
View Answer
Answer: d
Explanation: The grammar after the removal of epsilon production can be shown as:
S->ABaC| AaC| ABa| Aa| a| aC| Ba| BaC
A->BC| B| C
B->b
C->D
D-> d
9. Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a, B →b and E →c.
Number of productions in P’ after removal of useless symbols:
a) 4
b) 3
c) 2
d) 5
View Answer
Answer: a
Explanation:
P’= S->AB, A->a, B-> b,
V’={S, A, B},
∑’={a, b}
10. Given grammar G:
S->aS| AB
A-> e
B-> e
D-> b
Reduce the grammar, removing all the e productions:
a) S->aS| AB| A| B, D-> b
b) S->aS| AB| A| B| a, D-> b
c) S->aS| AB| A| B
d) None of the mentioned
View Answer
Answer: b
Explanation: We will replace all the nullables wherever they appear in the right hand side of any
production. D will not be erased as we are just removing nullable variables not completely simplifying the
grammar.

Automata Theory Questions and Answers – Eliminating Unit Productions

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Eliminating Unit
Productions”.

1. Which among the following is the format of unit production?

a) A->B
b) A->b
c) B->Aa
d) None of the mentioned
View Answer
Answer: a
Explanation: Any production of the format A-> B where A and B belongs to the V set, is called Unit
production.
2. Given Grammar G:
S->aA
A->a| A
B->B
The number of productions to be removed immediately as Unit productions:
a) 0
b) 1
c) 2
d) 3
View Answer
Answer: c
Explanation: The productions in the format A-> A are removed immediately as they produce self and that
is not a terminal or will not lead to a string. Hence, it is removed immediately.
3. Given grammar:
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
a) A
b) bb
c) aA
d) A| bb
View Answer
Answer: b
Explanation: The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb
4. If grammar G is unambiguous, G’ produced after the removal of Unit production will be:
a) ambiguous
b) unambiguous
c) finite
d) cannot be said
View Answer
Answer: b
Explanation: With the simplification of Context free grammars, undesirable properties are introduced. It
says, if grammar G, before simplification is unambiguous, after simplification will also be unambiguous.
5. If C is A-derivable, C->B is a production, and B ¹ A, then B is
a) nullable
b) Non-derivable
c) A-derivable
d) None of the mentioned
View Answer
Answer: c
Explanation:
If A-> B is a production, B is called A- derivable.
If C is A-derivable, C->B is a production, and B ¹ A, then B is A -derivable.
No other variables are A-derivable.
6. A can be A-> derivable if and only if __________
a) A-> A is actually a production
b) A->B, B-> A exists
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: a
Explanation: The format says: If A->B is a production, B is called A-derivable.Thus A to be A-derivable, a
production : A-> A need to exist.
7. Given Grammar:
T-> T+R| R
R-> R*V| V
V->(T)| u
When unit productions are deleted we are left with
T-> T+R| _______|(T)| u
R->R*V|(T)| u
V-> (T)| u
Fill in the blank:
a) T*V
b) T+V
c) R*T
d) R*V
View Answer
Answer: d
Explanation: The grammar produced after the elimination of unit production is:
T-> T+R| R*V| (T)| u
R->R*V|(T)| u
V-> (T)| u
advertisement

8. Given grammar G:
S-> ABA, A->aA|e, B-> bB|e
Eliminate e and unit productions. State the number of productions the starting variable holds?
a) 6
b) 7
c) 9
d) 5
View Answer
Answer: b
Explanation: After reduction the grammar looks like:
S->ABA| AB| BA| AA| Aa| a| bB| b
A->aA| a
B->bB| b
9. Given grammar G:
S-> A| B| C
A-> aAa| B
B-> bB|bb
C->aCaa|D
D->baD|abD|aa
Eliminate e and unit productions and state the number of variables left?
a) 5
b) 4
c) 3
d) 2
View Answer
Answer: 5
Explanation: The reduced production:
S->aAa| bB|bb aCaa| baD| abD| aa, A->aAa| bB| bb, B->bB| bb, C->aCaa| baD| abD| aa, D-> baD| abD|
aa
10. Which of the following variables in the given grammar is called live variable?
S->AB
A->a
a) S
b) A
c) B
d) None of the mentioned
View Answer
Answer: b
Explanation: Any variable A for which there is a production A-> x with x Ε Σ* is called live.

Automata Theory Questions and Answers – Chomsky Normal Form

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Chomsky Normal
Form”.

1. The format: A->aB refers to which of the following?

a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) None of the mentioned
View Answer
Answer: b
Explanation: A context free grammar is in Greibach Normal Form if the right hand sides of all the
production rules start with a terminal, optionally followed by some variables.
2. Which of the following does not have left recursions?
a) Chomsky Normal Form
b) Greibach Normal Form
c) Backus Naur Form
d) All of the mentioned
View Answer
Answer: b
Explanation: The normal form is of the format:
A->aB where the right hand side production tends to begin with a terminal symbo, thus having no left
recursions.
3. Every grammar in Chomsky Normal Form is:
a) regular
b) context sensitive
c) context free
d) all of the mentioned
View Answer
Answer: c
Explanation: Conversely, every context frr grammar can be converted into Chomsky Normal form and to
other forms.
4. Which of the production rule can be accepted by Chomsky grammar?
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
View Answer
Answer: d
Explanation: in CNF, the production rules are of the form:
A->BC
A-> a
S->e
5. Given grammar G:
(1)S->AS
(2)S->AAS
(3)A->SA
(4)A->aa
Which of the following productions denies the format of Chomsky Normal Form?
a) 2,4
b) 1,3
c) 1, 2, 3, 4
d) 2, 3, 4
View Answer
Answer: a
Explanation: The correct format: A->BC, A->a, X->e.
6. Which of the following grammars are in Chomsky Normal Form:
a) S->AB|BC|CD, A->0, B->1, C->2, D->3
b) S->AB, S->BCA|0|1|2|3
c) S->ABa, A->aab, B->Ac
d) All of the mentioned
View Answer
Answer: a
Explanation: We can eliminate the options on the basis of the format we are aware of: A->BC, B->b and
so on.
7. With reference to the process of conversion of a context free grammar to CNF, the number of variables
to be introduced for the terminals are:
S->ABa
A->aab
B->Ac
a) 3
b) 4
c) 2
d) 5
View Answer
Answer: a
Explanation: According to the number of terminals present in the grammar, we need the corresponding
that number of terminal variables while conversion.
advertisement

8. In which of the following, does the CNF conversion find its use?
a) CYK Algorithm
b) Bottom up parsing
c) Preprocessing step in some algorithms
d) All of the mentioned
View Answer
Answer: d
Explanation: Besides the theoretical significance of CNF, it conversion scheme is helpful in algorithms as
a preprocessing step, CYK algorithms and the bottom up parsing of context free grammars.
9. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in
___________.
a) restricted form
b) parsed form
c) normal form
d) all of the mentioned
View Answer
Answer: c
Explanation: When the production in G satisfy certain restrictions, then G is said to be in ‘normal form’.
10. Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?
a) Yes
b) No
View Answer
Answer: a
Explanation: e is allowed in CNF only if the starting variable does not occur on the right hand side of the
derivation.
Automata Theory Questions and Answers – Pumping Lemma for Context Free Language

This set of Automata Theory Questions and Answers for Campus interviews focuses on “Pumping
Lemma for Context Free Language”.

1. Which of the following is called Bar-Hillel lemma?

a) Pumping lemma for regular language
b) Pumping lemma for context free languages
c) Pumping lemma for context sensitive languages
d) None of the mentioned
View Answer
Answer: b
Explanation: In automata theory, the pumping lemma for context free languages, also kmown as the Bar-
Hillel lemma, represents a property of all context free languages.
2. Which of the expressions correctly is an requirement of the pumping lemma for the context free
languages?
a) uv nwxny
b) uv nwnxny
c) uv2nwx2ny
d) All of the mentioned
View Answer
Answer: b
Explanation: Let L be a CFL. Then there is an integer n so that for any u that belong to language L
satisfying |t| >=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy
|vx|>0
|vwx|<=n For any m>=0, uv nwxny ∈ L
3.Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying
|t|>=n, there are strings u, v, w, x, y and z satisfying
t=uvwxy.
Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of p :
a) 2p
b) 2p
c) 2p+1
d) p2
View Answer
Answer: c
Explanation: This inequation has been derived from derivation tree for t which must have height at least
p+2(It has more than 2p leaf nodes, and therefore its height is >p+1).
4. Which of the following gives a positive result to the pumping lemma restrictions and requirements?
a) {aibici|i>=0}
b) {0i1i|i>=0}
c) {ss|s∈{a,b}*}
d) None of the mentioned
View Answer
Answer: b
Explanation: A positive result to the pumping lemma shows that the language is a CFL and ist
contradiction or negative result shows that the given language is not a Context Free language.
5. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?
a) {aibici|i>=0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
d) None of the mentioned
View Answer
Answer: d
Explanation: There are few rules in C that are context dependent. For example, declaration of a variable
before it can be used.
6. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.
a) true
b) false
View Answer
Answer: b
Explanation: Although the pumping lemma provides some information about v and x that are pumped, it
says little about the location of these substrings in the string t. It can be used whenever the pumping
lemma fails. Example: {apbqcrds|p=0 or q=r=s}, etc.
7. Which of the following cannot be filled in the blank below?
Statement: There are CFLs L1 nad L2 so that ___________is not a CFL.
a) L1∩L2
b) L1′
c) L1*
d) None of the mentioned
View Answer
Answer: c
Explanation: A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
advertisement
8. The pumping lemma is often used to prove that a language is:
a) Context free
b) Not context free
c) Regular
d) None of the mentioned
View Answer
Answer: b
Explanation: The pumping lemma is often used to prove that a given language L is non-context-free, by
showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside
L.
9. What is the pumping length of string of length x?
a) x+1
b) x
c) x-1
d) x2
View Answer
Answer: a
Explanation: There exists a property of all strings in the language that are of length p, where p is the
constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L
plus 1.
10. Which of the following does not obey pumping lemma for context free languages ?
a) Finite languages
b) Context free languages
c) Unrestricted languages
d) None of the mentioned
View Answer
Answer: c
Explanation: Finite languages (which are regular hence context free ) obey pumping lemma where as
unrestricted languages like recursive languages do not obey pumping lemma for context free languages.

Automata Theory Questions and Answers – CFL- Closure Properties/Decision Properties

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “CFL- Closure
Properties/Decision Properties”.

1. The context free languages are closed under:

a) Intersection
b) Complement
c) Kleene
d) None of the mentioned
View Answer
Answer: c
Explanation: Context free languages are closed under the following operation: union, kleene and
concatenation. For regular languages, we can add intersection and complement to the list.
2. Given Grammar G1:
S->aSb
S->e
Grammar G2:
R->cRd
R->e
If L(G)=L(G1) U L(G2), the number of productions the new starting variable would have:
a) 2
b) 3
c) 4
d) 1
View Answer
Answer: a
Explanation:
T->S|R
S->aSb
S->e
R->cRd
R->e
3. Context free languages are not closed under:
a) Intersection
b) Intersection with Regular Language
c) Complement
d) All of the mentioned
View Answer
Answer: d
Explanation: It is a theorem which states that, Context free languages are not closed under operations
like intersection and complement.
4. Which of the following is incorrect?
There exists algorithms to decide if:
a) String w is in CFL L
b) CFL L is empty
c) CFL L is infinite
d) All of the mentioned
View Answer
Answer: d
Explanation: These properties are termed as decision properties of a CFL and include a set of problems
like infiniteness problem, emptiness problem and membership problem.
5. If the start symbol is one of those symbols which produce no terminal through any sequence, the CFL
is said to be
a) nullable
b) empty
c) eliminated
d) none of the mentioned
View Answer
Answer: b
Explanation: In the process of removing useless symbols, if the starting symbol is also a part, the CFL
can be then termed as empty; otherwise not.
6. Using the pumping constant n, If there is a string in the language of length between _____ and ____
then the language is infite else not.
a) n, 2n-1
b) 2n, n
c) n+1, 3n+6
d) 0, n+1
View Answer
Answer: a
Explanation: If there is a string in the language of length between n and 2n-1 then the language is infite
else not. The idea is essentially the same for regular languages.
7. Which of the following is/are CFL not closed under?
a) Reverse
b) Homomorphism
c) Inverse Homomorphism
d) All of the mentioned
View Answer
Answer: d
Explanation: CFL is closed under union, kleene and concatenation along with the properties
reversal,homomorphism and inverse homomorphism but not difference and intersection.
advertisement

8. If L1 and L2 are context free languages, L1-L2 are context free:

a) always
b) sometimes
c) never
d) none of the mentioned
View Answer
Answer: c
Explanation: Context free languages are not closed under difference, intersection and complement
operations.
9. A___________ is context free grammar with atmost one non terminal in the right handside of the
production.
a) linear grammar
b) linear bounded grammar
c) regular grammar
d) none of the mentioned
View Answer
Answer: a
Explanation: A simple linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules
S → aSb
S→ε
10. There is a linear grammar that generates a context free grammar
a) always
b) never
c) sometimes
d) none of the mentioned
View Answer
Answer: c
Explanation: Linear grammar is a subset of context free grammar which has atmost one non terminal
symbol in the right hand side of the production.Thus, there exists some languages which are generated
by Linear grammars

Automata Theory Questions and Answers – CFL- Other Normal Forms

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “CFL- Other
Normal Forms”.

1. The following format of grammatical notation is accepted by which of the following:

AB->CD
A->BC or
A->B or
A->a
where A, B, C, D are non terminal symbols and a is a terminal symbol.
a) Greibach Normal Form
b) Chomsky Nrmal Form
c) Kuroda Normal Form
d) None of the mentioned
View Answer
Answer: c
Explanation: Linearly Bounded grammar or Kuroda Normal Form allows the following format of
grammatical analysis:
AB->CD
A->BC or
A->B or
A->a
2. Every Kuroda Normal form grammar generates ___________
a) Context free grammar
b) Context sensitive grammar
c) Unrestricted grammar
d) None of the mentioned
View Answer
Answer: b
Explanation: Every context sensitive grammar which does not produce an empty string can be generated
by a grammar in Kuroda Normal form.
3. Which of the following can generate Unrestricted grammars?
a) Pentonnen Normal form
b) Floyd Normal form
c) Greibach Normal form
d) None of the mentioned
View Answer
Answer: a
Explanation: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight
modification in the format of Kuroda Normal form.
AB->AD
A->BC
A->a
4. Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will
halt at depth n.
a) top-down parser
b) bottom-up parser
c) multitape turing machine
d) none of the mentioned
View Answer
Answer: a
Explanation: Given a grammar in GNF and a derivable string in the grammar with the length n, any top-
down parser will halt at depth n. As the parameter ‘depth’ is mentioned, we will use a top-down parser.
Example-LL parser.
5. Which of the following grammars is similar to Floyd Normal form?
a) Backus Naur Form
b) Kuroda Normal Form
c) Greibach Normal Form
d) Chomsky Normal Form
View Answer
Answer: a
Explanation: Donald Knuth implied a BNF” syntax in which all definitions have such a form may be said to
be in ”Floyd Normal Form”.
A->B|C
A->BC
A->a
6. Which among the following can parse a context free grammar?
a) top down parser
b) bottom up parser
c) CYK algorithm
d) all of the mentioned
View Answer
Answer: d
Explanation: We use certain algorithms to parse a context free grammar which include the most popular
CYK algorithm which employs the concept of bottom up parsing and dynamic parsing.
7. The standard version of CYK algorithm operates only on context free grammars in the following form:
a) Greibach Normal form
b) Chomsky Normal form
c) Backus Naur form
d) All of the mentioned
View Answer
Answer: b
Explanation: It requires the presence of a context free grammar into Chomsky Normal form to operate.
However, every context free grammar can be converted into CNF for keeping the sense of grammar
equivalent.
advertisement

8. The __________ running time of CYK is O(n3 .|G|)

where n is the length of the parse string and |G| is the size of the context free grammar G.
a) worst
b) best
c) average
d) none of the mentioned
View Answer
Answer: a
Explanation: This is the worst case running time of CYK and and this makes it one of the most efficient
algorithms for recognizing general context free languages in practice.
9. Which of the following is true for Valiants algorithm?
a) an extension of CYK
b) deals with efficient multiplication algorithms
c) matrices with 0-1 entries
d) all of the mentioned
View Answer
Answer: d
Explanation: Valiants algorithm is actually an extention of CYK which even computes the same parsing
table yet he showed another method can be utilized fro performing this operation.
10. Which among the following is a correct option in format for representing symbol and expression in
Backus normal form?
a) <symbol> ->expression
b) <symbol>::=_expression_
c) <symbol>=<expression>
d) all of the mentioned
View Answer
Answer: b
Explanation: <symbol>::=_expression_ is the correct representation where <symbol> is a non terminal,
and expression consist of one or more sequence of symbols, more sequence are separated by |,
indicating a choice.

Automata Theory Questions and Answers – Intersection with Regular Languages

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Intersection with
Regular Languages”.

1. Which of the following is not a negative property of Context free languages?

a) Intersection
b) Complement
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Context free languages are not closed under complement and intersection. Thus, are called
Negative properties.
2. The intersection of context free language and regular language is _________
a) regular language
b) context free language
c) context sensitive language
d) non of the mentioned
View Answer
Answer: b
Explanation: If a language L1 is regular and L2 is a context free language, then L1 intersection L2 will
result into a context free language.
3. Which of the following is regular?
a) a100b100
b) (a+b)*-{a100b100}
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: As the language seems to be finite, a dfa can be constructed for the same, thus is regular.
4. Which of the following is not context free?
a) {w: nA=nB=nC}
b) {a*b*c*}
c) {a100b100}
d) All of the mentioned
View Answer
Answer: d
Explanation: {a*b*c*} and (c) are regular languages while option (a) is not context free language.
5. Which of the following can be used to prove a language is not context free?
a) Ardens theorem
b) Power Construction method
c) Regular Closure
d) None of the mentioned
View Answer
Answer: c
Explanation: We can use the properties of regular closure to prove that a language is not a context free
language. Example: Intersection of context free language and regular language is a context free
language. Proof by contradiction helps here.
6. Which of the following are valid membership algorithms?
a) CYK algorithm
b) Exhaustive search parser
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: CYK algorithm is a parsing algorithm for context free grammars, which employs bottom up
parsing and dynamic programming.
7. Which of the following belong to the steps to prove emptiness?
a) Remove useless variable
b) Check if a start variable S is useless
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: The empty-language question can be stated as: For context free grammar G find if L(G) =f?
advertisement

8. Which of the following is true for CYK Algorithm?

a) Triangular Table
b) Circular Chart
c) Linked List
d) None of the mentioned
View Answer
Answer: a
Explanation: A triangular table is constructed to facilitate the solution of membership problem using
bottom up parsing and dynamic programming.
9. Which of the following steps are wrong with respect to infiniteness problem?
a) Remove useless variables
b) Remove unit and epsilon production
c) Create dependency graph for variables
d) If there is a loop in the dependency graph the the language is finite else infinite
View Answer
Answer: d
Explanation: If we are able to detect a loop in the formed dependency graph, then the language in infinite.
10. State true or false:
Statement: Every context free language can be generated by a grammar which contains no useless non
terminals.
a) true
b) false
View Answer
Answer: a
Explanation: At first, we detect useless symbols and discard them. Inorder to find whether a symbol is
useless, just make it the starting symbol and check for emptiness.