Automata Theory Multiple Choice Questions & Answers (MCQs) “Finite Automata-Introduction”.
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive
Explanation: A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.
2. The non- Kleene Star operation accepts the following string of
finite length over set A = {0,1} | where string s contains even number
of 0 and 1
a) 01,0011,010101
b) 0011,11001100
c) ε,0011,11001100
d) ε,0011,11001100
Explanation: The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.
3. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned
Explanation: Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.
4. Statement 1: A Finite automata can be represented graphically;
Statement 2: The nodes can be its states; Statement 3: The edges or
arcs can be used for transitions
Hint: Nodes and Edges are for trees and forests too.
Which of the following make the correct combination?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned
Explanation: It is possible to represent a finite automaton graphically, with nodes for states, and arcs for transitions.
5. The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1
b) 3
c) 5
d) 7
Explanation: According to the question, minimum of 3 states are required to recognize an octal number divisible by 3.
6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
Explanation: A FA can be represented as FA= (Q, ∑, δ, q0, F) where Q=Finite Set of States, ∑=Finite Input Alphabet, δ=Transition Function, q0=Initial State, F=Final/Acceptance State).
7. If an Infinite language is passed to Machine M, the subsidiary
which gives a finite solution to the infinite input tape is
______________
a) Compiler
b) Interpreter
c) Loader and Linkers
d) None of the mentioned
Explanation: A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.
8. The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is_________
a) 7
b) 6
c) 8
d) 5
Explanation: ∑r= {1,0} and a Kleene* operation would lead to the following set=COUNT{ε,0,1,00,11,01,10} =7.
9. For the following change of state in FA, which of the following codes is an incorrect option?
a) δ (m, 1) =n
b) δ (0, n) =m
c) δ (m,0) =ε
d) s: accept = false; cin >> char;
if char = “0” goto n;
Explanation: δ(QX∑) = Q1 is the correct representation of change of state. Here, δ is called the Transition function.
10. Given: ∑= {a, b}
L= {xϵ∑*|x is a string combination}
∑4 represents which among the following?
a) {aa, ab, ba, bb}
b) {aaaa, abab, ε, abaa, aabb}
c) {aaa, aab, aba, bbb}
d) All of the mentioned
Explanation: ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x ϵ I.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Extended Transition Function”.
1. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4
Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.
2. Choose the correct option for the given statement:
Statement: The DFA shown represents all strings which has 1 at second last position.
a) Correct
b) Incorrect, Incomplete DFA
c) Wrong proposition
d) May be correct
Explanation: The given figure is an NFA. The statement contradicts itself.
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
Explanation: 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) =Upϵs δ (p, a)
b) δ’ (S, a) =Up≠s δ (p, a)
c) δ’ (S, a) =Upϵs δ(p)
d) δ’ (S) =Up≠s δ(p)
Explanation: 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
Explanation: 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.
6. If a string S is accepted by a finite state automaton, S=s1s2s3……sn where siϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:
a) initial state
b) transition symbol
c) accepting state
d) intermediate state
Explanation: 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).
7. According to the given table, compute the number of transitions with 1 as its symbol but not 0:
a) 4
b) 3
c) 2
d) 1
Explanation: The transition graph is made and thus the answer can be found.
8. From the given table, δ*(q0, 011) =?
a) {q0}
b) {q1} U {q0, q1, q2}
c) {q2, q1}
d) {q3, q1, q2, q0}
Explanation: δ*(q0,011) = Urϵδ*(q0,01) δ (r, 1) = {q0, q1, q2}.
9. Number of times the state q3 or q2 is being a part of extended 6 transition state is
a) 6
b) 5
c) 4
d) 7
Explanation: According to the question, presence of q2 or q1 would count so it does and the answer according to the diagram is 6.
10. Predict the missing procedure:
1.Δ(Q0, ε) ={Q0},
2.Δ(Q0, 01) = {Q0, Q1}
3.δ(Q0, 010) =?
a) {Q0, Q1, Q2}
b) {Q0, Q1}
c) {Q0, Q2}
d) {Q1, Q2}
Explanation: According to given table and extended transition state implementation, we can find the state at which it rests.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Regular Expression-Introduction”.
1. L is a regular Language if and only If the set of __________ classes of IL is finite.
a) Equivalence
b) Reflexive
c) Myhill
d) Nerode
Explanation: According to Myhill Nerode theorem, the corollary proves the given statement correct for equivalence classes.
2. A language can be generated from simple primitive language in a simple way if and only if
a) It is recognized by a device of infinite states
b) It takes no auxiliary memory
c) Both are correct
d) Both are wrong
Explanation: A language is regular if and only if it can be accepted by a finite automaton. Secondly, It supports no concept of auxiliary memory as it loses the data as soon as the device is shut down.
3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
Explanation: The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.
4. According to the given language, which among the following expressions does it corresponds to?
Language L={xϵ{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+ε)4
Explanation: The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.
5. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {xϵ {0,1} *|x is all binary number with even length}
b) {xϵ {0,1} |x is all binary number with even length}
c) {xϵ {0,1} *|x is all binary number with odd length}
d) {xϵ {0,1} |x is all binary number with odd length}
Explanation: The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.
6. If R represents a regular language, which of the following represents the Venn-diagram most correctly?
a) An Irregular Set
b) R*
c) R complement
d) R reverse
Explanation: The given diagram represents the Kleene operation over the Regular Language R in which the final states become the initial and the initial state becomes final.
7. The given NFA corresponds to which of the following Regular expressions?
a) (0+1) *(00+11) (0+1) *
b) (0+1) *(00+11) *(0+1) *
c) (0+1) *(00+11) (0+1)
d) (0+1) (00+11) (0+1) *
Explanation: The transition states shown are the result of breaking down the given regular expression in fragments. For dot operation, we change a state, for union (plus) operation, we diverge into two transitions and for Kleene Operation, we apply a loop.
8. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct
Explanation: Two operands are said to be performing Concatenation operation AB = A•B = {xy: x ∈ A & y ∈ B}.
9. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned
Explanation: By distributive property (Regular expression identities), we can prove the given identity to be Ф.
10. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R
Explanation: RR*=R+ as R+ means the occurrence to be at least once.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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
Explanation: 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
Explanation: 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
Explanation: 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
Explanation: 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
Explanation: 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)*
Explanation: 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
Explanation: 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
Explanation: None.
9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
Explanation: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
Explanation: According to definition of regular expression.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Pumping Lemma for Regular Language”.
1. Relate the following statement:
Statement: All sufficiently long words in a regular language can have a
middle section of words repeated a number of times to produce a new word
which also lies within the same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
Explanation: Pumping lemma defines an essential property for every regular language in automata theory. It has certain rules which decide whether a language is regular or not.
2. While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into _________ parts.
a) 2
b) 5
c) 3
d) 6
Explanation: We select a string w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL.
3. If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned
Explanation: The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0, this condition needs to be fulfilled to check the conclusion condition.
4. Let w= xyz and y refers to the middle portion and |y|>0.What do
we call the process of repeating y 0 or more times before checking that
they still belong to the language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
Explanation: The process of repeatation is called pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.
5. There exists a language L. We define a string w such that w∈L and
w=xyz and |w| >=n for some constant integer n.What can be the maximum
length of the substring xy i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
Explanation: It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the maximum length of the substring xy in w can be n only.
6. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______
a) p*1
b) p+1
c) p-1
d) None of the mentioned
Explanation: Finite languages trivially satisfy the pumping lemma by having n equal to the maximum string length in l plus 1.
7. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0
Explanation: Suppose L is a regular language . Then there is an integer n so that for any x∈L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ∈L.
8. If d is a final state, which of the following is correct according to the given diagram?
a) x=p, y=qr, z=s
b) x=p, z=qrs
c) x=pr, y=r, z=s
d) All of the mentioned
Explanation: The FSA accepts the string pqrs. In terms of pumping lemma, the string pqrs is broken into an x portion an a, a y portion qr and a z portion s.
9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does these variables represent?
a) string count
b) string
c) both (a) and (b)
d) none of the mentioned
Explanation: Given: w =xyz. Here, xyz individually represents strings or rather substrings which we compute over conditions to check the regularity of the language.
10. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container must contain more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned
Explanation: Pigeon hole principle states the following example: If there exists n=10 pigeons in m=9 holes, then since 10>9, the pigeonhole principle says that at least one hole has more than one pigeon.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Reversal-Homomorphism and Inverse Homomorphism”.
1. If L is a language, the reversal of the language can be represented as:
a) L’
b) Lc
c) Lr
d) more than one option is correct
Explanation: Lr is defined as the reversal of a language. Lr is a set of strings whose reversal is in L.
Example: L={0, 01, 100}
Lr={0, 10, 001}
2. If L is a regular language, ____ is also regular.
a) Lr
b) L’
c) L*
d) All of the mentioned
Explanation: Lr, L’, L* i.e. reversal, complementation and kleene all are the closure properties of regular language.
3. If E=F+G;
Er=?
a) Fr+Gr
b) (F+G)r
c) Both (a) and (b)
d) None of the mentioned
Explanation: If E is a symbol a, e, or f, then Er=E. Other inductive properties include union of reversals, concatenation and Kleene.
4. If E= FG, Er=?
a) FrGr
b) GrFr
c) Both (a) and (b)
d) None of the mentioned
Explanation: If E= FG, Er=GrFr . Example: (01*)R=(1*)R(0)R
5. Simplify the following identity:
E=01*+10*
ER=?
a) (1*0+0*1)
b) (01*10*)R
c) (0*1+10*)
d) All of the mentioned
Explanation: 01*+10*
ER=(01*)R+(10*)R=>(1*)R0R+(0*)R1R=>1*0+0*1
6. Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned
Explanation: Homomorphism on an aphabet is a function that gives a string for each symbol in that alphabet. Example: h(0)=ab, etc.
7. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned
abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.
8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)=_______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned
Explanation: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).
9. While proving Inverse Homomorphism, which of the following steps are needed?
a) Start with a DFA Ain L
b) Construct a DFA B for h-1(L)
c) The set of states, initial and final states should be same.
d) All of the mentioned
Explanation: While constructing DFA B, we need to take care of the following:
a) The same set of states
b) The same start state
c) The same final state
d) Input alphabet = the symbols to which homomorphism h applies.
10. 8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)= the language of two zeroes and any number of one’s.
The given example belongs to which of the following?
a) Homomorphism
b) Inverse Homomorphism
c) Both (a) and (b)
d) None of the mentioned
Explanation: Let h be a homomorphism and L a language whose alphabet is the output language of h.
h-1(L) = {w | h(w) is in L}.
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
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
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
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
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
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+ ∑
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
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.
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
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
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
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.
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
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
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
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
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
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
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
Explanation: 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
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
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
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.
This set of Automata Theory Questions and Answers for Entrance exams focuses on “PDA-Acceptance by Final State”.
1. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack
Explanation: A push down automata uses a stack to carry out its operations. They are more capable than the finite automatons but less than the turing model.
2. State true or false:
Statement: The operations of PDA never work on elements, other than the top.
a) true
b) false
Explanation: The term pushdown refers to the fact that the elements are pushed down in the stack and as per the LIFO principle, the operation is always performed on the top element of the stack.
3. Which of the following allows stacked values to be sub-stacks rather than just finite symbols?
a) Push Down Automaton
b) Turing Machine
c) Nested Stack Automaton
d) None of the mentioned
Explanation: In computational theory, a nested stack automaton is a finite automaton which makes use of stack containing data which can be additional stacks.
4. A non deterministic two way, nested stack automaton has n-tuple definition. State the value of n.
a) 5
b) 8
c) 4
d) 10
Explanation: The 10-tuple can be stated as: NSA= ‹Q,Σ,Γ,δ,q0,Z0,F,[,],]›.
5. Push down automata accepts _________ languages.
a) Type 3
b) Type 2
c) Type 1
d) Type 0
Explanation: Push down automata is for Context free languages and they are termed as Type 2 languages according to Chomsky hierarchy.
6. The class of languages not accepted by non deterministic, nonerasing stack automata is _______
a) NSPACE(n2)
b) NL
c) CSL
d) All of the mentioned
Explanation: NSPACE or non deterministic space is the computational resource describing the memory space for a non deterministic turing machine.
7. A push down automaton with only symbol allowed on the stack along with fixed symbol.
a) Embedded PDA
b) Nested Stack automata
c) DPDA
d) Counter Automaton
Explanation: This class of automata can recognize a set of context free languages like {anbn|n belongs to N}
8. Which of the operations are eligible in PDA?
a) Push
b) Delete
c) Insert
d) Pop
Explanation: Push and pop are the operations we perform to operate a stack. A stack follows the LIFO principle, which states its rule as: Last In First Out.
9. A string is accepted by a PDA when
a) Stack is empty
b) Acceptance state
c) Both (a) and (b)
d) None of the mentioned
Explanation: When we reach the acceptance state and find the stack to be empty, we say, the string has been accepted by the push down automata.
10. The following move of a PDA is on the basis of:
a) Present state
b) Input Symbol
c) Both (a) and (b)
d) None of the mentioned
Explanation: The next operation is performed by PDA considering three factors: present state,symbol on the top of the stack and the input symbol.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Deterministic PDA”
1. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
Explanation: A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.
2. A PDA machine configuration (p, w, y) can be correctly represented as:
a) (current state, unprocessed input, stack content)
b) (unprocessed input, stack content, current state)
c) (current state, stack content, unprocessed input)
d) none of the mentioned
Explanation: A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).
3. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned
Explanation: A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)
4. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
Explanation: The empty stack in the end is our requirement relative to finite state automatons.
5. A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
Explanation: A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.
6. State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
a) true
b) false
Explanation: There exists two lemma’s such that:
a) Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence
7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
d) none of the mentioned
Explanation: To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M, by both acceptance criteria.
8. A language accepted by Deterministic Push down automata is closed under which of the following?
a) Complement
b) Union
c) Both (a) and (b)
d) None of the mentioned
Explanation: Deterministic Context free languages(one accepted by PDA by final state), are drastically different from the context free languages. For example they are closed under complementation and not union.
9. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
Explanation: JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.
10. Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned
Explanation: The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.
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
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
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
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
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
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
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
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
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
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.
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
Explanation: In the process of removal of useless symbols, we want to remove productions that can never take part in any derivation.
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
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) uvnwxny
b) uvnwnxny
c) uv2nwx2ny
d) All of the mentioned
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, uvnwxny ∈ 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
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
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
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
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
Explanation: 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
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
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
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.
This set of Automata Theory Interview Questions and Answers for freshers focuses on “Turing Machine – Notation and Transition Diagrams”.
1. A turing machine is a
a) real machine
b) abstract machine
c) hypothetical machine
d) more than one option is correct
Explanation: A turing machine is abstract or hypothetical machine thought by mathematician Alan Turing in 1936 capable of simulating any algorithm, however complicated it is.
2. A turing machine operates over:
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
Explanation: The turing machine operates on an infinite memory tape divided into cells. The machine positions its head over the cell and reads the symbol.
3. Which of the functions are not performed by the turing machine after reading a symbol?
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned
Explanation: After the read head reads the symbol from the input tape, it performs the following functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.
4. ‘a’ in a-machine is :
a) Alan
b) arbitrary
c) automatic
d) None of the mentioned
Explanation: The turing machine was invented by Alan turing in 1936. He named it as a-machine(automatic machine).
5. Which of the problems were not answered when the turing machine was invented?
a) Does a machine exists that can determine whether any arbitrary machine on its tape is circular.
b) Does a machine exists that can determine whether any arbitrary machine on its tape is ever prints a symbol
c) Hilbert Entscheidungs problem
d) None of the mentioned
Explanation: Invention of turing machine answered a lot of questions which included problems like decision problem, etc.) . Alan was able to prove the properties of computation using such model.
6. The ability for a system of instructions to simulate a Turing Machine is called _________
a) Turing Completeness
b) Simulation
c) Turing Halting
d) None of the mentioned
Explanation: Turing Completeness the ability for a system of instructions to simulate a Turing machine. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.
7. Turing machine can be represented using the following tools:
a) Transition graph
b) Transition table
c) Queue and Input tape
d) All of the mentioned
Explanation: We can represent a turing machine, graphically, tabularly and diagramatically.
8. Which of the following is false for an abstract machine?
a) Turing machine
b) theoretical model of computer
c) assumes a discrete time paradigm
d) all of the mentioned
Explanation: A n abstract machine also known as abstract computer, is a theoretical model of computer or hardware system in automata theory. Abstraction in computing process usually assumes a discrete time paradigm.
9. Fill in the blank with the most appropriate option.
Statement: In theory of computation, abstract machines are often used in
___________ regarding computability or to analyze the complexity of an
algorithm.
a) thought experiments
b) principle
c) hypothesis
d) all of the mentioned
Explanation: A thought experiment considers some hypothesis, theory or principle for the purpose of thinking through its consequences.
10. State true or false:
Statement: RAM model allows random access to indexed memory locations.
a) true
b) false
Explanation: In computer science, Random access machine is an abstract machine in the general class of register machines. Random access machine should not be confused with Random access memory.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Multitape Turing Machines”.
1. A turing machine with several tapes in known as:
a) Multi-tape turing machine
b) Poly-tape turing maching
c) Universal turing machine
d) All of the mentioned
Explanation: A multitape turing machine is an ordinary turing machine with multiple tapes. Each tape has its own head to control the read and write.
2. A multitape turing machine is ________ powerful than a single tape turing machine.
a) more
b) less
c) equal
d) none of the mentioned
Explanation: The multitape turing machine model seems much powerful than the single tape model, but any multi tape machine, no matter how many tapes, can be simulated by single taped TM.
3. In what ratio, more computation time is needed to simulate multitape turing machines using single tape turing machines?
a) doubly
b) triple
c) quadratically
d) none of the mentioned
Explanation: Thus, multitape turing machines cannot calculate any more functions than single tape machines.
4. Which of the following is true for two stack turing machines?
a) one read only input
b) two storage tapes
c) Both (a) and (b)
d) None of the mentioned
Explanation: Two-stack Turing machines have a read-only input and two storage tapes. If a head moves left on either tape a blank is printed on that tape, but one symbol from a “library” can be printed.
5. Which of the following is not a Non deterministic turing machine?
a) Alternating Turing machine
b) Probabalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
Explanation: A read only turing machine or 2 way deterministic finite automaton is a class of model of computability that behaves like a turing machine, and can move in both directions across input, except cannot write to its input tape.
6. Which of the turing machines have existential and universal states?
a) Alternating Turing machine
b) Probalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
Explanation: ATM is divide into two sets: an existential state is accepting if some transitions leads to an accepting state; an universal state is accepting if every transition leads to an accepting state.
7. Which of the following is false for Quantum Turing machine?
a) Abstract machine
b) Any quantum algorithm can be expressed formally as a particular quantum turing machine
c) Gives a solution to ‘Is a universal quantum computer sufficient’
d) None of the mentioned
Explanation: ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from physics.
8. A deterministic turing machine is:
a) ambiguous turing machine
b) unambiguous turing machine
c) non-deterministic
d) none of the mentioned
Explanation: A deterministic turing machine is unambiguous and for every input, there is exactly one operation possible. It is a subset of non-deterministic Turing machines.
9. Which of the following is true about Turing’s a-machine?
a) a stands for automatic
b) left ended, right end-infinite
c) finite number of tape symbols were allowed
d) all of the mentioned
Explanation: Turings a- machine or automatic machine was left ended,right end infinite.Any of finite number of tape symbols were allowed and the 5 tuples were not in order.
10. Which of the following is a multi tape turing machine?
a) Post turing Machine
b) Wang-B Machine
c) Oblivious turing Machine
d) All of the mentioned
Explanation: An oblivious turing machine where movements of various heads are fixed functions of time, independent of the input. Pippenger and Fischer showed that any computation that can be performed by a multi-tape Turing machine in n steps can be performed by an oblivious two-tape Turing machine in O(n log n) steps.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Diagonalization Languages”
1. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?
a) Diagonalization
b) Recursive Induction
c) Both (a) and (b)
d) None of the mentioned
Explanation: To find a non recursively ennumerable language, we use the technique of diagonalization.
2. Diagonalization can be useful in:
a) To find a non recursively ennumerable language
b) To prove undecidablility of haltig problem
c) Both (a) and (b)
d) None of the mentioned
Explanation: Diagonalization is a technique we use for the following operations:
a) To find a non recursively ennumerable language.
b) To prove undecidablility of halting problem.
3. Which of the following are undecidable problems?
a) Determining whether two grammars generate the same language
b) Determining whether a grammar is ambiguous
c) Both (a) and (b)
d) None of the mentioned
Explanation: In contrast we can put up an algorithm for checking whether two FA’s are equivalent and this program can be implemented as a program.
4. Which of the following are incorrect options?
a) Informally, problem is a yes/no question about an infinite set of possible instances
b) Formally, a problem is a language
c) Both (a) and (b)
d) None of the mentioned
Explanation: Example: Does a graph G has a Hamilton cycle?
=>Each undirected graph is an instance of Hamilton cycle problem.
5. If a problem has an algorithm to answer it, we call it _________
a) decidable
b) solved
c) recognizable
d) none of the mentioned
Explanation: An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.
6. Which of the following are decidable problems?
a) Can a particular line of code in a program ever be executed?
b) Do two given CFG’s generate the same language
c) Is a given CFG ambiguous?
d) None of the mentioned
Explanation: All of the mentioned problems are undecidable.
7.Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
a) A concrete undecidable problem
b) A is recognizable but not decidable
c) -A is not recognizable
d) All of the mentioned
Explanation: We can proof A to be undecidable using the contradiction method.
8. Which of the following are correct statements?
a) TMs that always halt are known as Decidable problems
b) TMs that are guaranteed to halt only on acceptance are recursive ennumerable.
c) Both (a) and (b)
d) None of the mentioned
Explanation: There are two types of TMs on the basis of halting: Recursive and Recursively Ennumerable(TM may or may not halt,could loop forever).
9. Statement: If L id R.E., Lc needs to be R.E. Is it correct?
a) Yes
b) No
c) Maybe
d) Cannot predict
Explanation: Any recursive ennumerable language is not closed under complementation.
10. Which of the following is true for The Halting problem?
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned
Explanation: Halting problem: Does a given Turing machine M halt on a given input w?
11. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
a) true
b) false
Explanation: When turing machines are coded as Binary strings, we are restricted to take any input alphabet except {0,1}.
Explanation: It makes sense to talk about the i-th binary string” and about “the i-th Turing machine. If i makes no sense as a TM, assume the i-th TM accepts nothing.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Rice’s Theorem, Properties and PCP”.
1. According to the rice’s theorem, If P is a non trivial property, Lp is :
a) infinite
b) decidable
c) undecidable
d) none of the mentioned
Explanation: Rice’s theorem states that ‘Any non trivial property about the language recognized by a turing machine is undecidable’.
2. Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective
method can decide whether an algorithm computes it with that property.
a) partial functions
b) piecewise functions
c) both (a) and (b)
d) none of the mentioned
Explanation: A property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm.
3. Which of the following is incorrect according to rice theorem?
Let S be a set of language hat is non trivial:
a) there exists a TM that recognizes the language in S
b) there exists a TM that recognizes the language not in S
c) both (a) and (b)
d) none of the mentioned
Explanation: According to rice theorem, it is undecidable to determine whether the language recognized by an arbitrary turing machine lies in S.
4. Which of the following set of computable functions are decidable?
a) The class of computable functions that are constant, and its complement
b) The class of indices for computable functions that are total
c) The class of indices for recursively enumerable sets that are cofinite
d) All of the mentioned
Explanation: According to Rice’s theorem, if there exists atleast one computable function in a particular class C of computable functions and another computable function not in C then the problem deciding whether a particular program computes a function in C is undecidable.
5. Which of the following statements are undecidable?
For a given Turing Machine M,
a) does M halt on an empty input tape
b) does M halt for anly inputs at all?
c) is L(M) regular? Context free? Turing decidable?
d) all of the mentioned
Explanation: All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
6. Post Correspondence problem is
a) decidable decision problem
b) undecidable decision problem
c) not a decision problem
d) none of the mentioned
Explanation: Post Correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Being simpler than halting problem, it can be used in proofs of undecidability.
7. State true or false:
Statement: The difference between PCP and MPCP is that in MPCP, a
solution is required to start with the first string on each list.
a) true
b) false
Explanation: The MPCP is : Given lists A and B of K strings ,say A = w1 ,w2, …wk and B= x1, x2,…..xk does there exists a sequence of integers i1,i2,…ir such that w1wi1wi2…..wir = x1xi1xi2…xir?
8. PCP stands for?
a) Post Correspondence Problem
b) Post Corresponding Problem
c) Pre Correspondence problem
d) None of the mentioned
Explanation: PCP or Post Correspondence problem is an undecidable decision problem.
9. Can a Modified PCP problem be reduced to PCP?
a) yes
b) no
Explanation: Yes, it can be. There exists a theorem and as well as its proof which supports the assertion.
10. Consider three decision problem A, B, C. A is decidable and B is not. Which of the following is a correct option?
a) C is undecidable if C is reducible to B
b) C is undecidable if B is reducible to C
c) C is decidable if A is reducible to C
d) C is decidable if C is reducible to B’s complement.
Explanation: As B is undecidable and it can be reduced to C, C is also an undecidable problem.
This set of Automata Theory Interview Questions and Answers for Experienced people focuses on “Problem Solvable in Polynomial Time”.
1. If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in:
a) non-polynomial time
b) polynomial time
c) infinite time
d) none of the mentioned
Explanation: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.
2. The value of constants like p and e can be calculated in:
a) polynomial time
b) non-polynomial time
c) cannot be calculated
d) none of the mentioned
Explanation: The value of such constants can be calculated using algorithms which have time complexity in terms if O(nk) i.e polynomial time.
3. Which of the following cannot be solved using polynomial time?
a) Linear Programming
b) Greatest common divisor
c) Maximum matching
d) None of the mentioned
Explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.
4. The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.
a) Push Down automata
b) DFA
c) NDFA
d) Deterministic Turing machine
Explanation: All the decision problems that can be solved using a Deterministic turing machine using polynomial time to compute, all belong to the complexity class P.
5. A generalization of P class can be:
a) PTIME
b) DTIME
c) NP
d) None of the mentioned
Explanation: P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.
6. Which of the following options are correct with reference to P-complete problems?
a) used for the problems which are difficult to solve in limited space
b) every problem in P can be reduced to it using proper reductions
c) complete problem for complexity class P
d) all of the mentioned
Explanation:
The notion of P-complete decision problems is useful in the analysis of:
a) which problems are tough to parallelize effectively
b) which problems are difficult to solve in limited space
7. A problem X belongs to P complexity class if there exist ________
algorithm to solve that problem, such that the number of steps of the
algorithms bounded by a polynomial in n, where n is the length of the
input.
a) 1
b) 2
c) 3
d) all of the mentioned
Explanation: A problem X belongs to P complexity class if there exist atleast 1 algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input. Thus, all the options are correct.
8. Which of the following is a P-complete type of problem?
a) Circuit Value problem
b) Linear programming
c) Context free grammar membership
d) All of the mentioned
Explanation: Given a context free grammar and a string, can the string be generated by the grammar? Such problems fall in the category of P-complete.
9. State true or false?
Statement: Given a turing machine, an input for the machine, and a
number T(unary), does that machine halt on that input within the first
T-steps?
The given problem is P-complete.
a) true
b) false
Explanation: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.
10. In the above problem, if the input is binary, the class the problem belongs?
a) EXPSPACE
b) DLOGTIME
c) EXPTIME-complete
d) All of the mentioned
Explanation: It is the set of all decision problems that have exponential run time i.e. solvable by deterministic turing machine in O(2p(n)) time, where p(n) is a polynomial function of n.
This set of Automata Theory Questions and Answers for Aptitude test focuses on “Node-Cover Problem, Hamilton Circuit Problem”.
1. Which of the given problems are NP-complete?
a) Node cover problems
b) Directed Hamilton Circuit Problem
c) Both (a) and (b)
d) None of the mentioned
Explanation: Vertex cover or Node cover problem, and Hamilton Circuit problem, both are NP complete type of problems.
2. Which of the following problems do not belong to Karp’s 21 NP-complete problems?
a) Vertex Cover problems
b) Knapsack
c) 0-1 integer programming
d) None of the mentioned
Explanation: There exists a set of 21 problems that are NP-complete and the set is called Karp’s 21 NP-complete problems.
3. Which of the following problems were reduced to Knapsack?
a) Exact Cover
b) Max Cut
c) 0-1 integer programming
d) None of the mentioned
Explanation: Exact cover is a decision problem in computer science to determine if an exact cover exists.
4. An exact cover problem can be represented using:
a) incidence matrix
b) bipartite graph
c) both (a) and (b)
d) none of the mentioned
Explanation: The relation ‘contains’ can be represented using a bipartite graph. The vertices of the graph can be divided into two disjoint sets, one representing the subset S and the other representing the elements of P and one edge for each subset in S;each node is included in exactly one of the edges forming the cover.
5. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?
a) tree graphs
b) bipartite graphs
c) both (a) and (b)
d) none of the mentioned
Explanation: For bipartite graphs, Konigs theorem allows the bipartite vertex problem to be solved in polynomial time.
6. Hamilton circuit problem can have the following version/s as per the input graph:
a) directed
b) undirected
c) both (a) and (b)
d) none of the mentioned
Explanation: Hamilton circuit problem is a problem determining whether a Hamiltonian path(a path in an undirected or directed graph that visits each vertex exactly once) exists in a graph(directed or undirected).
7. Hamilton Circuit problem is a special case of ____________
a) travelling salesman problem
b) halting problem
c) hitting set
d) none of the mentioned
Explanation: Hamilton circuit problem is a special case of travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
8. Which of the following cannot solve Hamilton Circuit problem?
a) DNA Computer
b) Monte Carlo algorithm
c) Dynamic programming
d) None of the mentioned
Explanation: Using Inclusion-exclusion principle, Andreas showed how to solve Hamilton Circuit problem in arbitrary n-vertex graphs by a Monte Carlo algorithm in time O(1.657n).
9. State true or false:
Statement: Hamiltonian cycles through any fixed edge is always even, so
if one such cycle is given, the second one must also exists.
a) true
b) false
Explanation: Handshaking lemma states that ‘Every finite undirected graph has an even number of vertices with odd degree.
10. Fibonacci number falls in the category of _________ combinatorics.
a) Algebric
b) Enumerative
c) Analytic
d) Extremal
Explanation: Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Fibonacci series is a basic example of Enumerative Combinatorics.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “PSPACE”.
1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:
a) PSPACE
b) NPSPACE
c) EXPSPACE
d) None of the mentioned
Explanation: PSPACE is the problem class which contains all set of decision problems which can be solved using a turing machine taking polynomial amount of space.
2. PSPACE is strictly the super set of:
a) Regular language
b) Context free language
c) Context Sensitive Language
d) None of the mentioned
Explanation: Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -complete problem.
3. Savitch theorem relates to which of the following:
a) PSPACE=NPSPACE
b) Alternating Turing Machine
c) Time complexity
d) None of the mentioned
Explanation: Some important conclusions of Savitch theorem includes:
a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.
b) NL∈L2
4. The class PSPACE is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
d) All of the mentioned
Explanation: The closure property of PSPACE class includes :- Union, Concatenation and Kleene operation.
5. Correct the given order:
NL∈ P∈ NP∈ PH∈ PSPACE
a) NP∈ P∈ NL∈ PH∈ PSPACE
b) NL∈ PH∈ NP∈ P∈ PSPACE
c) NL∈ P∈ NP∈ PH∈ PSPACE
d) None of the mentioned
Explanation: The given order is the only correct order and further PSPACE belongs to EXPTIME class and subsequently occurs EXPSPACE class.
6. NL ∈ PSPACE ∈ EXPSPACE
The given relation involves which of the following theorems?
a) Space hierarchy theorem
b) Savitch’s theorem
c) Both (a) and (b)
d) None of the mentioned
Explanation: From space hierarchy theorem: NL ∈ NPSPACE, from Savitch’s theorem: NPSPACE= PSPACE.
7. Statement : All PSPACE problems can be reduced to PSPACE-complete problems.
State true or false:
a) true
b) false
Explanation: PSPACE-complete problems are the most difficut problems is PSPACE. Finding a simple solution to PSPACE-complete means simple solution to all other problems in PSPACE because all PSPACE problems can be reduced to PSPACE-complete problems.
8. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.
a) time
b) space
c) both time and space
d) none of the mentioned
Explanation: Though it may use extra time, but as PSPACE=NPSPACE from savitch’s theorem, we can say that space taken is same for both the machins, deterministic as well as non-deterministic.
9. Complement of all the problems in PSPACE is ________
a) PSPACE
b) NL
c) P
d) All of the mentioned
Explanation: The complement of all the problems in PSPACE are also in PSPACE, meaning co-PSPACE= PSPACE.
10. Which of the following PSPACE can be characterized into?
a) APTIME
b) AP
c) Quantom complexity class
d) None of the mentioned
Explanation: An alternative characterization of PSPACE is a set of problems decidable by a turing machine in polynomial time, sometimes called, APTIME or AP.
This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Complexity Classes,Class RP and ZPP”.
1. Which among the following is smallest for n=50
a) 2n2
b) n2+3n+7
c) n3
d) 2n
Explanation:
2n2=5000
n2+3n+7=2567
n3=125000
2n=1.13*1015
2. The space complexity of a turing machine is undefined if:
a) It is a multitape turing machine
b) If no string of length n causes T to use infinite number of tape squares
c) If some input of length n causes T to loop forever
d) None of the mentioned
Explanation: If there exists an input string of length n that causes T to use an infinite number of tape squares, the space complexity of the turing machine is undefined.
3. In order to reduce the run time of a turing machine:
a) we can reduce the number of tapes
b) we can increase the number of tapes
c) use infinite tapes
d) none of the mentioned
4. Which of the following are basic complexity classes for a function f:N->N?
a) Ntime(f)
b) Nspace(f)
c) Space(f)
d) All of the mentioned
Explanation: Ntime(f): is a set of languages that can be accepted by a NTM T with non deterministic time complexity function t <=f. In all four cases, the machines are allowed to be multitape TM’s.
5. A function f is called __________ if there exists a TM T so that
for any n and any input string of length n, T halts in exactly f(n)
moves.
a) Step function
b) Step counting function
c) Inplace functions
d) None of the mentioned
Explanation: If f is a step counting function, T is a TM halting in f(n) moves where n is the length of input string.
6. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)
a) O(nf)
b) O(n+f)
c) O(n2f2)
d) None of the mentioned
Explanation: Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn2(f(n))2 is the total number of moves required.
7. Which among the following is false?
If f=O(h) and g=O(k) for f,g,h,k:N->N, then
a) f+g = O(h+k)
b) fg = O(hk)
c) fg=O(hk)
d) None of the mentioned
Explanation: f,g,h,k are partial functions and each is defined at all but a finite number of points.
8. Which of the following is not correct for ZPP?
a) zero error probabalistic polynomial time
b) it runs in non-polynomial time
c) it returns an answer yes, no or do not know
d) none of the mentioned
Explanation: ZPP is zero error probabalistic polynomial time complexity class which run in polynomial time, returns an answer: yes, no or do not know.
9. ZPP is based on ________
a) Probabalistic turing machine
b) Alternative turing machine
c) Quantum turing machine
d) None of the mentioned
Explanation: A probabalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probability distribution.
10. ZPP is exactly equal to the ____________of the classes RP and co-RP.
a) Union
b) Intersection
c) Concatenation
d) Difference
Explanation: To prove the following statement, we need to take in note that every problem in RP and co-RP has a Las-Vegas algorithm.
11. Suppose we have a las vegas algorithm C to prove ZPP is contained
in RP and co-RP. Run C for double its expected running time.
By Markov’s inequality, the chance that it will answer before we stop is:
a) 1/2
b) 1/4
c) 1/3
d) none of the mentioned
Explanation: This means the chance we’ll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm.
Explanation: ZPP is said to be closed under complement function i.e. ZPP=co-ZPP.
