Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions 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

Answer: b
Clarification: 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

Answer: b
Clarification: 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

Answer: c
Clarification: 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

Answer: d
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: According to the number of terminals present in the grammar, we need the corresponding that number of terminal variables while conversion.

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

Answer: d
Clarification: 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

Answer: c
Clarification: 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

Answer: a
Clarification: e is allowed in CNF only if the starting variable does not occur on the right hand side of the derivation.

1. Which among the following are semi decidable?
a) Empty-DFA
b) Rec-NFA
c) Infinite-DFA
d) All of the mentioned

Answer: d
Clarification: All are the properties of regular languages and all are decidable languages.

2. The language accepted by a turing machine is called ____________
a) Recursive Ennumerable
b) Recursive
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: The language accepted by Turing machines are called recursively ennumerable (RE), and the subset of RE languages that are accepted by a turing machine that always halts are called recursive.

3. Decidable can be taken as a synonym to:
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned

Answer: a
Clarification: We can refer to languages as ‘recursive’ and problems as ‘decidable’. If a language is not recursive , then we call the problem expressed by that language undecidable.

4. The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:
a) Decidable
b) Undecidable
c) Computable
d) None of the mentioned

Answer: b
Clarification: The problems that can be solved by a turing machine can divided into two classes:
a) Those that have an algorithm
b) Intractable problems: Those that are only solved by a turing machine that may run forever on inputs they do not accept.

5. An algorithm is called efficient if it runs in ____________ time on a serial computer.
a) polynomial
b) non polynomial
c) logarithmic
d) none of the mentioned

Answer: a
Clarification: Example: Runtimes of efficient algorithms
O(n), O(nlogn), O(n³log2ⁿ)
Runtimes of inefficient algorithms
O(2ⁿ), O(n!)

6. A problem is called __________ if its has an efficient algorithm for itself.
a) tractable
b) intractable
c) computational
d) none of the mentioned

Answer: a
Clarification: A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.

7. A formal language is recursive if :
a) a total turing machine exists
b) a turing machine that halts for every input
c) turing machine rejects if the input does not belong to the language
d) all of the mentioned

Answer: d
Clarification: A formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

8. Recursive languages are also known as:
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned

Answer: a
Clarification: A language is recursive if there exists a turing machine such that it halts i.e. accepts if the input belongs to the language else rejects. It is better called Turing decidable language.

9. The class of recursive language is known as:
a) R
b) RC
c) RL
d) All of the mentioned

Answer: a
Clarification: R is the set of all recursive languages, a class of decision problems solvable by turing machines. Although, R is also used for the class RP.

10. Which of the following was not a part of Chomsky hierarchy ?
a) Context sensitive grammar
b) Unrestricted grammar
c) Recursive grammar
d) None of the mentioned

Answer: c
Clarification: All recursive languages are recursively enumerable. All regular, context free and context sensitive languages are recursive.

Automata Theory Multiple Choice Questions on “Extended Transition Function”.

1. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4

Answer: a
Clarification: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.

2. If a string S is accepted by a finite state automaton, S=s₁s₂s₃……s_n where s_iϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), s_i+1) =r_i+1 for each 0, 1, …n-1, then r(n) is:
a) initial state
b) transition symbol
c) accepting state
d) intermediate state

Answer: c
Clarification: r(n) is the final state and accepts the string S after the string being traversed through r(i) other states where I ϵ 01,2…(n-2).

3. What is wrong in the given definition?
Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})
a) The definition does not satisfy 5 Tuple definition of NFA
b) There are no transition definition
c) Initial and Final states do not belong to the Graph
d) Initial and final states can’t be same

Answer: c
Clarification: q3 does not belong to Q where Q= set of finite states.

4. If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:
Note: S is a subset of Q and a is a symbol.
a) δ’ (S, a) =U_pϵs δ (p, a)
b) δ’ (S, a) =U_p≠s δ (p, a)
c) δ’ (S, a) =U_pϵs δ(p)
d) δ’ (S) =U_p≠s δ(p)

Answer: a
Clarification: According to subset construction, equation 1 holds true.

5. What is the relation between DFA and NFA on the basis of computational power?
a) DFA > NFA
b) NFA > DFA
c) Equal
d) Can’t be said

Answer: c
Clarification: DFA is said to be a specific case of NFA and for every NFA that exists for a given language, an equivalent DFA also exists.

Automata Theory Multiple Choice Questions on “Converting Regular Expressions to Automata”.

1. What kind of expressions do we used for pattern matching?
a) Regular Expression
b) Rational Expression
c) Regular & Rational Expression
d) None of the mentioned

Answer: c
Clarification: In automata theory, Regular Expression(sometimes also called the Rational Expression ) is a sequence or set of characters that define a search pattern, mainly for the use in pattern matching with strings or string matching.

2. Which of the following do Regexps do not find their use in?
a) search engines
b) word processors
c) sed
d) none of the mentioned

Answer: d
Clarification: Regexp processors are found in several search engines, seach and replace mechanisms, and text processing utilities.

3. Which of the following languages have built in regexps support?
a) Perl
b) Java
c) Python
d) C++

Answer: a
Clarification: Many languages come with built in support of regexps like Perl, Javascript, Ruby etc. While some provide support using standard libraries like .NET, Java, Python, C++, C and POSIX.

4. The following is/are an approach to process a regexp:
a) Contruction of NFA and subsequently, a DFA.
b) Thompson’s Contruction Algorithm
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: A regexp processor translates the syntax into internal representation which can be executed and matched with a string and that internal representation can have several approaches like the ones mentioned.

5. Are the given two patterns equivalent?
(1) gray|grey
(2) gr(a|e)y
a) yes
b) no

Answer: a
Clarification: Paranthesis can be used to define the scope and precedence of operators. Thus, both the expression represents the same pattern.

6. Which of the following are not quantifiers?
a) Kleene plus +
b) Kleene star *
c) Question mark ?
d) None of the mentioned

Answer: d
Clarification: A quantifier after a token specifies how often the preceding element is allowed to occur. ?, *, +, {n}, {min, }, {min, max} are few quantifiers we use in regexps implementations.

7. Which of the following cannot be used to decide whether and how a given regexp matches a string:
a) NFA to DFA
b) Lazy DFA algorithm
c) Backtracking
d) None of the mentioned

Answer: d
Clarification: There are at least three algorithms which decides for us, whether and how a regexp matches a string which included the transformation of Non deterministic automaton to deterministic finite automaton, The lazy DFA algorithm where one simulates the NFA directly, building each DFA on demand and then discarding it at the next step and the process of backtracking whose running time is exponential.

8. What does the following segment of code output?

$string1 = "Hello Worldn";
if ($string1 =~ m/(H..).(l..)/) {
  print "We matched '$1' and '$2'.n";
}

a) We matched ‘Hel’ and ‘ld’
b) We matched ‘Hel’ and ‘lld’
c) We matched ‘Hel’ and ‘lo ‘
d) None of the mentioned

Answer: c
Clarification: () groups a series of pattern element to a single element.
When we use pattern in parenthesis, we can use any of ‘$1’, ‘$2’ later to refer to the previously matched pattern.

9. Given segment of code:

$string1 = "HellonWorldn";
if ($string1 =~ m/dnz/) {
  print "$string1 is a string ";
  print "that ends with 'd\n'.n";
}

What does the symbol /z does?
a) changes line
b) matches the beginning of a string
c) matches the end of a string
d) none of the mentioned

Answer: c
Clarification: It matches the end of a string and not an internal line.The given segment of code outputs:
Hello
World
is a string that ends with ‘dn’

10. Conversion of a regular expression into its corresponding NFA :
a) Thompson’s Construction Algorithm
b) Powerset Construction
c) Kleene’s algorithm
d) None of the mentioned

Answer: a
Clarification: Thompson construction algorithm is an algorithm in automata theory used to convert a given regular expression into NFA. Similarly, Kleene algorithm is used to convert a finite automaton to a regular expression.

Automata Theory Multiple Choice Questions 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

Answer: b
Clarification: 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

Answer: b
Clarification: 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

Answer: c
Clarification: 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

Answer: b
Clarification: 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

Answer: d
Clarification: 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

Answer: b
Clarification: 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

Answer:
Clarification: LALR stands for Look ahead left to right parsers. It has more language recognition power than LR(0) parser.

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

Answer: c
Clarification: 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

Answer: d
Clarification: 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

Answer: c
Clarification: 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 for Campus interviews 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

Answer: b
Clarification: 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ⁿwxⁿy
b) uvⁿwⁿxⁿy
c) uv²ⁿwx²ⁿy
d) All of the mentioned

Answer: b
Clarification: 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|=0, uvⁿwxⁿy ∈ 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) p²

Answer: c
Clarification: This inequation has been derived from derivation tree for t which must have height at least p+2(It has more than 2^p 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) {aⁱbⁱcⁱ|i>=0}
b) {0ⁱ1ⁱ|i>=0}
c) {ss|s∈{a,b}*}
d) None of the mentioned

Answer: b
Clarification: 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) {aⁱbⁱcⁱ|i>=0}
b) {ss|s∈{a,b}*}
c) The set legal C programs
d) None of the mentioned

Answer: d
Clarification: 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

Answer: b
Clarification: 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: {a^pb^qc^rd^s|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

Answer: c
Clarification: A set of context free language is closed under the following operations:
a) Union
b) Concatenation
c) Kleene

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

Answer: b
Clarification: 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

Answer: a
Clarification: 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

Answer: c
Clarification: 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.