Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Regular Language & Expression”.

1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11

Answer: c
Clarification: string of length 0 = Not possible (because y is always present).
string of length 1 = 1 (y)
string of length 2 = 3 (xy,yy,ya)
string of length 3 = 8 (xxy,xyy,yxy,yyy,yaa,yab,xya,yya)

2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned

Answer: d
Clarification: None.

3. A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine

Answer: a
Clarification: All of above machine can accept regular language but all string accepted by machine is regular only for DFA.

4. Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned

Answer: a
Clarification: Regular grammar is subset of context free grammar.

5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2

Answer: d
Clarification: Finite state machine and regular expression have same power to express a language.

6. Which of the following is not a regular expression?
a) [(a+b)*-(aa+bb)]*
b) [(0+1)-(0b+a1)*(a+b)]*
c) (01+11+10)*
d) (1+2+0)*(1+2)*

Answer: b
Clarification: Except b all are regular expression*.

7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language

Answer: a
Clarification: According to Chomsky hierarchy .

8. Which of the following is true?
a) Every subset of a regular set is regular
b) Every finite subset of non-regular set is regular
c) The union of two non regular set is not regular
d) Infinite union of finite set is regular

Answer: b
Clarification: None.

9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive

Answer: d
Clarification:If L is recursive enumerable and its complement too if and only if L is recursive.

10. Regular expressions are closed under
a) Union
b) Intersection
c) Kleen star
d) All of the mentioned

Answer: d
Clarification: According to definition of regular expression.

Automata Theory Question Bank 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

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

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

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

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

Answer: a
Clarification: 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|>=2^h, then its parse tree’s height is at least _____
a) h
b) h+1
c) h-1
d) 2^h

Answer: b
Clarification: It is the basic implication of Parse tree theorem (assuming CNF). If the height of the parse tree is h, then |w| <=2^h-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

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

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

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

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

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