Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Applications of NFA”.

1. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned

Answer: d
Clarification: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation.

2. It is less complex to prove the closure properties over regular languages using:
a) NFA
b) DFA
c) PDA
d) Can’t be said

Answer: a
Clarification: None.

3. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned

Answer: d
Clarification: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.

4. John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?
a) 9
b) 11
c) 12
d) 15

Answer: a
Clarification: None.

5. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method

Answer: c
Clarification: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.

6. Which among the following can be an example of application of finite state machine(FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned

Answer: a
Clarification: Idle is the state when data in form of packets is send and returns if NAK is received else waits for the NAK to be received.

7. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned

Answer: d
Clarification: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State charts, etc.

8. L1= {w | w does not contain the string tr }
L2= {w | w does contain the string tr}
Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?
a) 0
b) 1
c) 2
d) Cannot be said

Answer: a
Clarification: None.

9. Predict the number of transitions required to automate the following language using only 3 states:
L= {w | w ends with 00}
a) 3
b) 2
c) 4
d) Cannot be said

Answer: a
Clarification: None.

10. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13

Answer: a
Clarification: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this condition a finite automata can be created using 1 states.

Automata Theory Multiple Choice Questions & Answers on “Properties-Non Regular Languages”.

1. All the regular languages can have one or more of the following descriptions:
i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
Which of the following are correct?
a) i, ii, iv
b) i, ii, iii
c) i, iv
d) i, ii, iii, iv

Answer: d
Clarification: The class of languages known as the regular language has atleast four different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions

2. Which of the technique can be used to prove that a language is non regular?
a) Ardens theorem
b) Pumping Lemma
c) Ogden’s Lemma
d) None of the mentioned

Answer: b
Clarification: We use the powerful technique called Pumping Lemma, for showing certain languages not to be regular. We use Ardens theorem to find out a regular expression out of a finite automaton.

3. Which of the following language regular?
a) {aⁱbⁱ|i>=0}
b) {aⁱbⁱ|0<i<5}
c) {aⁱbⁱ|i>=1}
d) None of the mentioned

Answer: b
Clarification: Here, i has limits i.e. the language is finite, contains few elements and can be graphed using a deterministic finite automata. Thus, it is regular. Others can be proved non regular using Pumping lemma.

4. Which of the following are non regular?
a) The set of strings in {a,b}* with an even number of b’s
b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a
c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0.
d) None of the mentioned

Answer: d
Clarification: All of the given languages are regular and finite and thus, can be represented using respective deterministic finite automata. We can also use mealy or moore machine to represent remainders for option c.

5. If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned

Answer: b
Clarification: This is a simple example of a closure property: a property saying that the set of DFA-regular languages is closed under certain operations.

6. Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes.
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states.
c) A language L is NFA-regular if and only if it is DFA-regular.
d) None of the mentioned

Answer: b
Clarification: Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.

7. Myphill Nerode does the following:
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: In automata theory, the Myphill Nerode theorem provides a necessary and sufficient condition for a language to be regular. The Myphill Nerode theorem can be used to show a language L is regular by proving that the number of equivalence classes of R_L(relation) is finite.

8. Which of the following are related to tree automaton?
a) Myphill Nerode Theorem
b) State machine
c) Courcelle’s Theorem
d) All of the mentioned

Answer: d
Clarification: The myphill nerode theorem can be generalized to trees and an application of tree automata prove an algorithmic meta theorem about graphs.

9. Given languages:
i) {aⁿbⁿ|n>=0}
ii)

ⁿ
iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences
Which of the following is/are non regular?
a) i, iii
b) i
c) iii
d) i, ii, iii

Answer: d
Clarification: There is no regular expression that can parse HTML documents. Other options are also non-regular as they cannot be drawn into finite automaton.

10. Finite state machine are not able to recognize Palindromes because:
a) Finite automata cannot deterministically find the midpoint
b) Finite automata cannot remember arbitarily large amount of data
c) Even if the mid point is known, it cannot find whether the second half matches the first
d) All of the mentioned

Answer: d
Clarification: It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.

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