Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Uses of Epsilon-Transitions”.

1. The automaton which allows transformation to a new state without consuming any input symbols:
a) NFA
b) DFA
c) NFA-l
d) All of the mentioned

Answer: c
Clarification: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.

2. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned

Answer: b
Clarification: An epsilon move is a transition from one state to another that doesn’t require any specific condition.

3. The __________ of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.
a) e-closure
b) e-pack
c) Q in the tuple
d) None of the mentioned

Answer: a
Clarification: The e-closure of a set of states, P, of an NFAis defined as the set of states reachable from any state in P following e-transitions.

4. The e-NFA recognizable languages are not closed under :
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned

Answer: The languages which are recognized by an epsilon Non deterministic automata are closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Negation
e) Star
f) Kleene closure

5. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA?
a) yes
b) no

Answer: a
Clarification: Yes, the language is preserved during the dteps of construction: L(N)=L(N1)=L(N2)=L(3).

6. An e-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned

Answer: b
Clarification: An e-NFA consist of 5 tuples: A=(Q, S, d, q0, F)
Note: e is never a member of S.

7. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false

Answer: a
Clarification: e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.

Automata Theory Multiple Choice Questions on “Applications of Pumping Lemma/Pigeonhole principle”.

1. Which kind of proof is used to prove the regularity of a language?
a) Proof by contradiction
b) Direct proof
c) Proof by induction
d) None of the mentioned

Answer: a
Clarification: We use the method of proof by contradiction in pumping lemma to prove that a language is regular or not.

2. The language of balanced paranthesis is
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Answer: b
Clarification: Given n, there is a string of balanced parentheses that begins with more than p left parentheses, so that y will contain entirely of left parentheses. By repeating y, we can produce a string that does not contain the same number of left and right parentheses, and so they cannot be balanced.

3. State true or false:
Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.
a) true
b) false

Answer: a
Clarification: The converse of the lemma is not true. There may exists some language which satisfy all the conditions of the lemma and still be non-regular.

4. Which of the following is/are an example of pigeon hole principle?
a) Softball team
b) Sock picking
c) Hair counting
d) All of the mentioned

Answer: d
Clarification: There are several applications of pigeonhole principle:
Example: The softball team: Suppose 7 people who want to play softball(n=7 items), with a limitation of only 4 softball teams to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be atleast one team featuring atleast two of the seven players.

5. Pigeonhole principle can be applied in the following computer science algorithms:
a) hashing algorithm
b) lossless compression algorithm
c) both (a) and (b)
d) none of the mentioned

Answer: c
Clarification: Collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array.

6. If n objects are distributed over m places, and n < m, then some of the places receive:
a) at least 2 objects
b) at most 2 objects
c) no object
d) none of the mentioned

Answer: c
Clarification: This is one of the alternative formulations of the pigeon hole principle. As n < m, there will exist some place which will not receive any of the object.

7. Which of the following fields may have pigeonhole principle violated?
a) Discrete mathematics
b) Computer Science
c) Quantum Mechanics
d) None of the mentioned

Answer: c
Clarification: Y Aharonov proved mathematically the violation of pigeon hole principle in Quantum mechanics and proposed inferometric experiments to test it.

8. Which of the following is not an application of Pumping Lemma?
a) {0ⁱ1ⁱ|i>=0}
b) {0ⁱx|i>=0, x∈{0, 1}* and |x|<=i}
c) {0ⁿ| n is prime}
d) None of the mentioned

Answer: d
Clarification: None of the mentioned are regular language and are an application to the technique Pumping Lemma. Each one of the mentioned can be proved non regular using the steps in Pumping lemma.

9. Which of the following can refer a language to be non regular?
a) Pumping Lemma
b) Myphill Nerode
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: On the contrary, the typical way to prove that a language is to construct either a finite state machine or a regular expression for the language.

10. Which of the following is not an example of counting argument?
a) Pigeonhole principle
b) Dirichlet’s drawer principle
c) Dirichlet’s box principle
d) None of the mentioned

Answer: d
Clarification: Pigeon hole principle or Dirichlet’s drawer principle or Dirichlet’s box principle is an example of counting argument whose field is called Combinatorics.

Basic Automata Theory Questions and Answers on “From Grammars to Push Down Automata”.

1. The production of the form A->B , where A and B are non terminals is called
a) Null production
b) Unit production
c) Greibach Normal Form
d) Chomsky Normal Form

Answer: b
Clarification: A->ε is termed as Null production while A->B is termed as Unit production.

2. Halting states are of two types. They are:
a) Accept and Reject
b) Reject and Allow
c) Start and Reject
d) None of the mentioned

Answer: a
Clarification: Halting states are the new tuple members introduced in turing machine and is of two types: Accept Halting State and Reject Halting State.

3. A push down automata can be represented as:
PDA= ε-NFA +[stack]
State true or false:
a) true
b) false

4. A pushdown automata can be defined as: (Q, ∑, G, q0, z0, A, d)
What does the symbol z0 represents?
a) an element of G
b) initial stack symbol
c) top stack alphabet
d) all of the mentioned

Answer: d
Clarification: z0 is the initial stack symbol, is an element of G. Other symbols like d represents the transition function of the machine.

5. Which of the following correctly recognize the symbol ‘|-‘ in context to PDA?
a) Moves
b) transition function
c) or/not symbol
d) none of the mentioned

Answer: a
Clarification: Using this notation, we can define moves and further acceptance of a string by the machine.

6. Which among the following is true for the given statement?
Statement :If there are strings R and T in a language L so that R is prefix of T and R is not equivalent to T.
a) No DPDA can accept L by empty stack
b) DPDA can accept L by an empty stack
c) L is regular
d) None of the mentioned

Answer: a
Clarification: If M is a DPDA accepting L by an empty stsck, R and T are distinct strings in L, and R is a prefix of T, then the sequence of moves M must make in order to accept R leaves the stack empty, since R∈L. But then T cannot be accepted, since M cant move with an empty stack.

7. Which of the following can be accepted by a DPDA?
a) The set of even length palindrome over {a,b}
b) The set of odd length palindrome over {a,b}
c) {xx^c| where c stands for the complement,{0,1}}
d) None of the mentioned

Answer: d
Clarification: Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.

8. For a counter automaton, with the symbols A and Z0, the string on the stack is always in the form of __________
a) A
b) AⁿZ0, n>=0
c) Z0Aⁿ, n>=0
d) None of the mentioned

Answer: b
Clarification:The possible change in the stack contents is a change in the number of A’s on the stack.

9. State true or false:
Statement: Counter Automaton can exist for the language L={0ⁱ1ⁱ|i>=0}
a) true
b) false

Answer: a
Clarification: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the initial state and the only accepting state.

10. Let ∑={0,1}* and the grammar G be:
S->ε
S->SS
S->0S1|1S0
State which of the following is true for the given
a) Language of all and only Balanced strings
b) It contains equal number of 0’s and 1’s
c) Ambiguous Grammar
d) All of the mentioned

Answer: d
Clarification: A string is said to be balanced if it consist of equal number of 0’s and 1’s.

Automata Theory Questions and Answers for Freshers on ” The Language of Turing Machine″.

1. The class of recursively ennumerable language is known as:
a) Turing Class
b) Recursive Languages
c) Universal Languages
d) RE

Answer: d
Clarification: RE or recursively ennumerable is only called the class of recursively ennumerable language.

2. A language L is said to be Turing decidable if:
a) recursive
b) TM recognizes L
c) TM accepts L
d) None of the mentioned

Answer: a,b
Clarification: A language L is recursively ennumerable if there is a turing machine that accepts L, and recursive if there is a TM that recognizes L.(Sometimes these languages are alse called Turing-acceptable and Turing-decidable respectively).

3. Which of the following statements are false?
a) Every recursive language is recursively ennumerable
b) Recursively ennumerable language may not be recursive
c) Recursive languages may not be recursively ennumerable
d) None of the mentioned

Answer: c
Clarification: Every recursive language is recursively ennumerable but there exists recursively ennumerable languages that are not recursive. If L is accepted by a Non deterministic TM T, and every possible sequence of moves of T causes it to halt, then L is recursive.

4. Choose the correct option:
Statement: If L1 and L2 are recursively ennumerable languages over S, then the following is/are recursively ennumerable.
a) L1 U L2
b) L2 ∩ L2
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: Both the union and intersection operations preserve the property of recursive ennumerablity(Theorem).

5. If L is a recursive language, L’ is:
a) Recursive
b) Recursively Ennumerable
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: If T is a turing machine recognizing L, we can make it recognize L’ by interchanging the two outputs. And every recursive language is recursively ennumerable.

6. Choose the appropriate option:
Statement: If a language L is recursive, it is closed under the following operations:
a) Union
b) Intersection
c) Complement
d) All of the mentioned

Answer: d
Clarification: The closure property of recursive languages include union, intersection and complement operations.

7. A recursively ennumerable language L can be recursive if:
a) L’ is recursively ennumerable
b) Every possible sequence of moves of T, the TM which accept L, causes it to halt
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: Theorem- If L is a recursively ennumerable language whose complement is recursively ennumerable, then L is recursive.

8. State true or false:
Statement: An ennumerator is a turing machine mwith extra output tape T, where symbols, once written, are never changed.
a) true
b) false

Answer: a
Clarification: To ennumerate a set means to list the elements once at a time, and to say that a set is ennumerable should perhaps mean that there exists an algorithm for ennumerating it.

9. A Language L may not be accepted by a Turing Machine if:
a) It it is recursively ennumerable
b) It is recursive
c) L can be ennumerated by some turing machine
d) None of the mentioned

Answer: b
Clarification: A language L is recursively ennumerable if and only if it can be ennumerated by some turing machine. A recursive ennumerable language may or may not be recursive.

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

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

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

Answer: One way to reduce the run time can be to increase the number of tapes. Sometimes, using two tapes can be used to avoid back and forth motions altogether.

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

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

Answer: b
Clarification: 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(n²f²)
d) None of the mentioned

Answer: c
Clarification: Using the encoding function, it is possible to show that if the function f is a step counting function, then the function Cn²(f(n))² 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) f^g=O(h^k)
d) None of the mentioned

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

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

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

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

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

12. State true or false:
Statement: ZPP is closed under complement function.
a) true
b) false

Answer: a
Clarification: ZPP is said to be closed under complement function i.e. ZPP=co-ZPP.

Automata Theory Multiple Choice Questions on “Finite Automata-Introduction”.

1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive

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

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

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

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

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

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

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

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

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

Answer: b
Clarification: ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x ϵ I.