Category: Automata Theory Objective Questions

Automata Theory Questions and Answers for Entrance exams on “PDA-Acceptance by Final State”.

1. A push down automaton employs ________ data structure.
a) Queue
b) Linked List
c) Hash Table
d) Stack

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

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

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

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

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

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

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

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

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

Answer: c
Clarification: The next operation is performed by PDA considering three factors: present state,symbol on the top of the stack and the input symbol.

Automata Theory Interview Questions and Answers for freshers 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer: d
Clarification: An alternative characterization of PSPACE is a set of problems decidable by a turing machine in polynomial time, sometimes called, APTIME or AP.

Automata Theory test on “Finite Automata with Epsilon Transition”.

1. According to the given transitions, which among the following are the epsilon closures of q1 for the given NFA?
Δ (q1, ε) = {q2, q3, q4}
Δ (q4, 1) =q1
Δ (q1, ε) =q1
a) q4
b) q2
c) q1
d) q1, q2, q3, q4

Answer: d
Clarification: The set of states which can be reached from q using ε-transitions, is called the ε-closure over state q.

2. State true or false?
Statement: An NFA can be modified to allow transition without input alphabets, along with one or more transitions on input symbols.
a) True
b) False

Answer: a
Clarification: It is possible to construct an NFA with ε-transitions, presence of no input symbols, and that is called NFA with ε-moves.

3. State true or false?
Statement: ε (Input) does not appears on Input tape.
a) True
b) False
Answer: a

Clarification: ε does not appears on Input tape, ε transition means a transition without scanning a symbol i.e. without moving the read head.

4. Statement 1: ε- transition can be called as hidden non-determinism.
Statement 2: δ (q, ε) = p means from q it can jump to p with a shift in read head.
Which among the following options is correct?
a) Statement 1 and 2, both are correct
b) Statement 1 and 2, both are wrong
c) Statement 1 is correct while Statement 2 is wrong
d) Statement 1 is wrong while Statement 2 is correct

Answer: c
Clarification: The transition with ε leads to a jump but without any shift in read head. Further, the method can be called one to introduce hidden non-determinism.

5. ε- closure of q1 in the given transition graph:
a) {q1}
b) {q0, q2}
c) {q1, q2}
d) {q0, q1, q2}

Answer: c
Clarification: ε-closure is defined as the set of states being reached through ε-transitions from a starting state.

6. Predict the total number of final states after removing the ε-moves from the given NFA?
a) 1
b) 2
c) 3
d) 0

Answer: c
Clarification: The NFA which would result after eliminating ε-moves can be shown diagramatically.

7. For NFA with ε-moves, which among the following is correct?
a) Δ: Q X (∑ U {ε}) -> P(Q)
b) Δ: Q X (∑) -> P(Q)
c) Δ: Q X (∑*) -> P(Q)
d) All of the mentioned

Answer: a
Clarification: Due to the presence of ε symbol, or rather an epsilon-move, the input alphabets unites with it to form a set including ε.

8. Which among the following is false?
ε-closure of a subset S of Q is:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)
d) None of the mentioned

Answer: d
Clarification: All the mentioned are the closure properties of ε and encircles all the elements if it satisfies the following options:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)

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

10. 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 doesnt require any specific condition.

11. 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 NFA is defined as the set of states reachable from any state in P following e-transitions.

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

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

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

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

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

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

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

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

Answer: b
Clarification: 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 _______ xyⁱz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0

Answer: d
Clarification: 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, uv^mw ∈L.

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

Answer: a
Clarification: Given: w =xyz. Here, xyz individually represents strings or rather substrings which we compute over conditions to check the regularity of the language.

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

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

Automata Theory Multiple Choice Questions on “PDA-acceptance by Empty Stack”.

1. If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called
a) Complement
b) Union
c) Disjoint
d) Connected

Answer: c
Clarification: Two sets are called disjoint if they have no elements in common i.e. RÇT=Æ.

2. Which among the following is not a part of the Context free grammar tuple?
a) End symbol
b) Start symbol
c) Variable
d) Production

Answer: a
Clarification: The tuple definition of context free grammar is: (V, T, P, S) where V=set of variables, T=set of terminals, P=production, S= Starting Variable.

3. A context free grammar is a ___________
a) English grammar
b) Regular grammar
c) Context sensitive grammar
d) None of the mentioned

Answer: c
Clarification: Context free grammar is the set which belongs to the set of context free grammar. Similarly, Regular grammar is a set which belongs to the the set of Context free grammar.

4. The closure property of context free grammar includes :
a) Kleene
b) Concatenation
c) Union
d) All of the mentioned

Answer: d
Clarification: Context free grammars are closed under kleene operation, union and concatenation too.

5. Which of the following automata takes stack as auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned

Answer: b
Clarification: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.

6. Which of the following automata takes queue as an auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned

Answer: c
Clarification: Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.

7. A context free grammar can be recognized by
a) Push down automata
b) 2 way linearly bounded automata
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: A linearly bounded automata is a restricted non deterministic turing machine which is capable of accepting ant context free grammar.

8. A null production can be referred to as:
a) String
b) Symbol
c) Word
d) All of the mentioned

Answer: a
Clarification: Null production is always taken as a string in computational theory.

9. The context free grammar which generates a Regular Language is termed as:
a) Context Regular Grammar
b) Regular Grammar
c) Context Sensitive Grammar
d) None of the mentioned

Answer: b
Clarification: Regular grammar is a subset of Context free grammar. The CFGs which produces a language for which a finite automaton can be created is called Regular grammar.

10. NPDA stands for
a) Non-Deterministic Push Down Automata
b) Null-Push Down Automata
c) Nested Push Down Automata
d) All of the mentioned

Answer: a
Clarification: NPDA stands for non-deterministic push down automata whereas DPDA stands for deterministic push down automata.