Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Multistack Machines, Counter Machines”.

1. Can a single tape turing machine be simulated using deterministic 2-stack turing machine?
a) Yes
b) No
c) Cannot be said
d) none of the mentioned

Answer: a
Clarification: The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.

2. A ___________ is a multi tape turing machine whose input tape is read only.
a) Counter Machine
b) Multi-stack
c) Alternating Turing machine
d) None of the mentioned

Answer: a
Clarification: Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.

3. Instantaneous description of a counter machine can be described using:
a) the input tape contents
b) position of the input head
c) distance of storage heads from symbol Z
d) all of the mentioned

Answer: d
Clarification: Instantaneous description of a counter machine can be described by the state, the input tape contents, the position of input head, and the distance of storage heads from the symbol Z. The counter machine can really store a count on each tape and tell if the count is zero.

4. Which of the following parameters cannot be used to restrict a turing machine?
a) tape alphabets
b) number of tapes
c) number of states
d) none of these

Answer: d
Clarification: Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.

5. Linear Bounded Automaton is a:
a) Finite Automaton
b) Turing Machine
c) Push down Automaton
d) None of the mentioned

Answer: b
Clarification: Linear Bounded Automaton is a type of Turing Machine where tape is not allowed to move off the portion of the tape containing the input. It is a Turing machine with limited amount of memory.

6. State true or false:
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.
a) true
b) false

Answer: true
Clarification: A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.

7. Which of the following is true with reference to semi-infinite tape using a two track tape?
a) Can simulate a two way tape
b) Upper track represents the head-right cells
c) Lower track represents the head-left cells
d) All of the mentioned

Answer: d
Clarification: The upper track represents the cells of the original TM that are at the right of the initial head position. The lower track represents the cells to the left of the initial head position, but in reverse order.

8. Which among the following options are correct?
Statement 1: TMs can accept languages that are not accepted by any PDA with one stack.
Statement 2: But PDA with two stacks can accept any language that a TM can accept.
a) Statement 1 and 2, both are correct
b) Statement 1 is correct but Statement 2 is false
c) Statement 2 is correct while Statement 1 is false
d) Statement 1 and 2, both are false

Answer: a
Clarification: Both the statements are true. Both the statements are properties of Multistack machines.

9. A two-way infinite tape turing machine is ________ superior than the basic model of the turing machine in terms of power.
a) more
b) less
c) no way
d) none of the mentioned

Answer: c
Clarification: A two way infinite tape turing machine is a turing machine with its input tape infinte in both directions, the other component being the same as the basic model.

10. For a basic turing machine, there exists an equivalent :
a) 2-counter machine
b) 3-counter machine
c) 4-counter machine
d) All of the mentioned
Answer: d

Automata Theory Multiple Choice Questions on “The Language of DFA”

1. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite

Answer: d
Clarification: A language over an alphabet R is a set of strings over A which is uncountable and infinite.

2. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false

Answer: b
Clarification: Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.

3. δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set

Answer: a
Clarification: δ or the Transition function describes the best, how a DFA behaves on a string where to transit next, which direction to take.

4. Which of the following option is correct?
A= {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
c) ε may not belong to A
d) abca ₵ A

Answer: b
Clarification: As the question has dot operation, ε will not be a part of the concatenated set. Had it been a union operation, ε would be a part of the operated set.

5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?
a) 0
b) 0,2
c) 0,2,4
d) 0,1,2,3

Answer: d
Clarification: All the decimal numbers on division would lead to only 4 remainders i.e. 0,1,2,3 (Property of Decimal division).

6. The sum of minimum and maximum number of final states for a DFA n states is equal to:
a) n+1
b) n
c) n-1
d) n+2

Answer: a
Clarification: The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.

7. Given:
L1= {xϵ ∑*|x contains even no’s of 0’s}
L2= {xϵ ∑*|x contains odd no’s of 1’s}
No of final states in Language L1 U L2?
a) 1
b) 2
c) 3
d) 4
Answer: c

8. The maximum number of transition which can be performed over a state in a DFA?
∑= {a, b, c}
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.

9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:
∑= {a, b, c, d}
a) 4+4
b) 4+16
c) 4+0
d) depends on the Language

Answer: d
Clarification: The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over the Language.

Automata Theory MCQs on “Conversion by Eliminating states”.

1. Which of the following is an utility of state elimination phenomenon?
a) DFA to NFA
b) NFA to DFA
c) DFA to Regular Expression
d) All of the mentioned

Answer: c
Clarification: We use this algorithm to simplify a finite automaton to regular expression or vice versa. We eliminate states while converting a given finite automata to its corresponding regular expression.

2. If we have more than one accepting states or an accepting state with an outdegree, which of the following actions will be taken?
a) addition of new state
b) removal of a state
c) make the newly added state as final
d) more than one option is correct

Answer: d
Clarification: If there is more than one accepting state or if the single accepting state as an out degree , add a new accepting state, make all other states non accepting, and hold an e-transitions from each former accepting state to the new accepting state.

3. Which of the following is not a step in elimination of states procedure?
a) Unifying all the final states into one using e-transitions
b) Unify single transitions to multi transitions that contains union of input
c) Remove states until there is only starting and accepting states
d) Get the resulting regular expression by direct calculation

Answer: b
Clarification: While eliminating the states, we unify multiple transitions to one transition that contains union of input and not the vice versa.

4. Is it possible to obtain more than one regular expression from a given DFA using the state elimination method?
a) Yes
b) No

Answer: a
Clarification: Using different sequence of removal of state, we can have different possible solution of regular expressions. For n-state deterministic finite automata excluding starting and final states, n! Removal sequences are there. It is very tough to try all the possible removal sequences for smaller expressions.

5. Which of the following methods is suitable for conversion of DFA to RE?
a) Brzozowski method
b) Arden’s method
c) Walter’s method
d) All of the mentioned

Answer: a
Clarification: Brzozowski method takes a unique approach to generating regular expressions. We create a system of regular expressions with one regular expression unknown for each state in M, and then we solve the system for Rλ where Rλ is the regular expression associated with starting state qλ.

6. State true or false:
Statement: The state removal approach identifies patterns within the graph and removes state, building up regular expressions along each transition.
a) true
b) false

Answer: a
Clarification: This method has the advantage over the transitive closure technique as it can easily be visualized.

7. The behaviour of NFA can be simulated using DFA.
a) always
b) never
c) sometimes
d) none of the mentioned

Answer: a
Clarification: For every NFA, there exists an equivalent DFA and vice versa.

8. It is suitable to use ____________ method/methods to convert a DFA to regular expression.
a) Transitive Closure properties
b) Brzozowski method
c) State elimination method
d) All of the mentioned

Answer: d
Clarification: For converting RE to DFA , first we convert RE to NFA (Thompson Construction), and then NFA is converted into DFA(Subset Construction).

9. State true or false:
Statement: For every removed state, there is a regular expression produced.
a) true
b) false

Answer: a
Clarification: For every state which is eliminated, a new regular expression is produced. The newly generated regular expression act as an input for a state which is next to removed state.

Automata Theory Multiple Choice Questions on “Sentential Forms”.

1. State true or false:
Statement: Every right-linear grammar generates a regular language.
a) True
b) False

Answer: a
Clarification: A CFG is said to right linear if each production body has at most one variable, and that variable is at the right end. That is, all productions of a right linear grammar are of the form A->wB or A->w, where A and B are variables while w is some terminal.

2. What the does the given CFG defines?
S->aSbS|bSaS|e and w denotes terminal
a) wwr
b) wSw
c) Equal number of a’s and b’s
d) None of the mentioned

Answer: c
Clarification: Using the derivation approach, we can conclude that the given grammar produces a language with a set of string which have equal number of a’s and b’s.

3. If L1 and L2 are context free languages, which of the following is context free?
a) L1*
b) L2UL1
c) L1.L2
d) All of the mentioned

Answer: d
Clarification: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.

4. For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6

Answer: c
Clarification: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01

5. For the given Regular expression, the minimum number of terminals required to derive its grammar is:
(011+1)*(01)*
a) 4
b) 3
c) 5
d) 6

Answer: b
Clarification: The grammar can be written as:
S->BC
B->AB|ε
A->011|1
C->DC|ε
D->01

6. A grammar G=(V, T, P, S) is __________ if every production taken one of the two forms:
B->aC
B->a

a) Ambiguous
b) Regular
c) Non Regular
d) None of the mentioned

Answer: b
Clarification: The following format of grammar is of Regular grammar and is a part of Context free grammar i.e. like a specific form whose finite automata can be generated.

7. Which among the following is a CFG for the given Language:
L={x∈{0,1}*|number of zeroes in x=number of one’s in x}
a) S->e|0S1|1S0|SS
b) S->0B|1A|e A->0S B->1S
c) All of the mentioned

Answer: c
Clarification: We can build context free grammar through different approaches, recursively defining the variables and terminals inorder to fulfil the conditions.

8. Which of the following languages are most suitable for implement context free languages ?
a) C
b) Perl
c) Assembly Language
d) None of the mentioned

Answer: a
Clarification: The advantage of using high level programming language like C and Pascal is that they allow us to write statements that look more like English.

9. Which among the following is the correct grammar for the given language?
L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}
a) S-> 0|SS|1SS|SS1|S1S
b) S-> 1|0S|0SS|SS0|S0S
c) S-> 0|0S|1SS|SS1|S1S
d) None of the mentioned

Answer: c
Clarification: L={0, 1, 00, 11, 001, 010,…}
The grammar can be framed as: S-> 0|0S|1SS|SS1|S1S

10. L={0ⁱ1^j2^k | j>i+k}
Which of the following satisfies the language?
a) 0111100
b) 011100
c) 0001100
d) 0101010

Answer: a
Clarification: It is just required to put the value in the variables in the question and check if it satisfies or not.

Automata Theory Multiple Choice Questions on “Eliminating Epsilon Productions”.

1. The use of variable dependency graph is in:
a) Removal of useless variables
b) Removal of null productions
c) Removal of unit productions
d) None of the mentioned

Answer: a
Clarification: We use the concept of dependency graph inorder to check, whether any of the variable is reachable from the starting variable or not.

2. The variable which produces an epsilon is called:
a) empty variable
b) nullable
c) terminal
d) all of the mentioned

Answer: b
Clarification: Any variable A for which the derivation: A->*e is possible is called Nullable.

3. Statement:
For A-> e ,A can be erased. So whenever it appears on the left side of a production, replace with another production without the A.
State true or false:
a) true
b) false

Answer: b
Clarification: A can be erased. So whenever it appears on the right side of the production, replace with another production without the A.

4. Simplify the given grammar:
S->aXb
X->aXb | e
a) S->aXb | ab, X-> aXb | ab
b) S->X | ab, X-> aXb | ab
c) S->aXb | ab, X-> S | ab
d) None of the mentioned

Answer: a
Clarification: As X is nullable, we replace every right hand side presence of X with e and produce the simplified result.

5. Consider the following grammar:
A->e
B->aAbC
B->bAbA
A->bB
The number of productions added on the removal of the nullable in the given grammar:
a) 3
b) 4
c) 2
d) 0

Answer: b
Clarification: The modified grammar aftyer the removal of nullable can be shown as:
B->aAbC| abC
B->bAbA| bbA| bAb| bb
A->bB

6. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar G’ having no e productions.
a) e ∈ L(G)
b) w ∉ L(G)
c) e ∉ L(G)
d) w ∈ L(G)

Answer: c
Clarification: Theorem: Let G = (V, T, S, P) be a CFG such that e ∉ L(G). Then there exists an equivalent grammar G’ having no e-productions.

7. For each production in P of the form:
A-> x1x2x3…xn
put into P’ that production as well as all those generated by replacing null variables with e in all possible combinations. If all x(i) are nullable,
a) A->e is put into P’
b) A->e is not put into P’
c) e is a member of G’
d) None of the mentioned

Answer: b
Clarification: It is an exception that A->e is not put into P’ if all x(i) are nullable variables.

8. For the given grammar G:
S->ABaC
A->BC
B->b| e
C->D| e
D-> d
Remove the e productions and generate the number of productions from S in the modified or simplified grammar.
a) 6
b) 7
c) 5
d) 8

Answer: d
Clarification: The grammar after the removal of epsilon production can be shown as:
S->ABaC| AaC| ABa| Aa| a| aC| Ba| BaC
A->BC| B| C
B->b
C->D
D-> d

9. Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a, B →b and E →c.
Number of productions in P’ after removal of useless symbols:
a) 4
b) 3
c) 2
d) 5

Answer: a
Clarification:
P’= S->AB, A->a, B-> b,
V’={S, A, B},
∑’={a, b}

10. Given grammar G:
S->aS| AB
A-> e
B-> e
D-> b
Reduce the grammar, removing all the e productions:
a) S->aS| AB| A| B, D-> b
b) S->aS| AB| A| B| a, D-> b
c) S->aS| AB| A| B
d) None of the mentioned

Answer: b
Clarification: We will replace all the nullables wherever they appear in the right hand side of any production. D will not be erased as we are just removing nullable variables not completely simplifying the grammar.a

Automata Theory Multiple Choice Questions on “Simulation of Turing Machine”.

1. Fill in the blank with an appropriate option.
In automata theory, ___________ is said to be Computationally Universal if can be used to simulate any single taped Turing Machine.
a) Computer’s instruction set
b) A programming language
c) Cellular Automaton
d) All of the mentioned

Answer: d
Clarification: Computationally Universal or Turing Complete is a set of data manipulation rules if it can be used to simulate a single-taped turing machine.

2. Give a classic example of the concept of turing complete.
a) lambda calculus
b) C++
c) Lisp
d) All of the mentioned

Answer: d
Clarification: Most of the programming languages, conventional or unconventional are turing complete. Functional languages like Lisp and Haskell are also turing complete.

3. Let two machines be P and Q. The state in which P can simulate Q and Q can simulate P is called:
a) Turing Equivalence
b) State Equivalence
c) Universal Turing Machine
d) None of the mentioned

Answer: a
Clarification: It is a closely related concept with Turing complete. It says, two computers P and Q are called equivalent if P can simulate Q and Q can simulate P.

4. Which of the following remarks the given statement?
Statement: Any function whose values can be computed by an algorithm, can be computed by a Turing machine.
a) Smn theorem
b) Structured Program theorem
c) Church-Turing thesis
d) None of the mentioned

Answer: c
Clarification: The following conclusion is laid down from the Church-Turing thesis:
Any function whose values can be computed by an algorithm, can be computed by a Turing machine. If any real world computer can be simulated by a turing machine, it is Turing equivalent to a Turing Machine.

5. Which of the following can be used to simulate any turing machine?
a) Finite State Automaton
b) Universal Turing Machine
c) Counter machines
d) All of the mentioned

Answer: b
Clarification: The computational aspect of any possible real world computer can be simulated using an Universal Turing Machine so can be any turing machine.

6. State true or false:
Statement: Inorder to show something is Turing complete, it is enough to demonstrate that it can be used to simulate some Turing complete system.
a) true
b) false

Answer: a
Clarification: Yes it is. For instance, an imperative language is called Turing complete if it tends to have conditional branching and an ability to maintain an arbitrary number of symbols.

7. Which of the following can lack in a Universal computer?
a) Turing Complete Instruction set
b) Infinite memory
c) Infinite time
d) None of the mentioned

Answer: d
Clarification: Real computers which are manufactured till date, all are similar to single taped turing machine. However, they have limited physical resources so they are linearly bounded complete on the contrary.

8. Which among are not the results of computational theory?
a) In general, it is impossible to predict that what a Turing-complete program will do over an arbitrarily long time.
b) It is impossible to determine for every input, whether the program will eventually stop or continue forever.
c) It is not possible to determine whether a program will return true or false.
d) None of the mentioned

Answer: d
Clarification: All of the following mentioned are the conclusions of automata theory or computability theory.

9. Which of the games fill under the category of Turing-complete?
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) All of the mentioned

Answer: d
Clarification: Many games fall under the category og turing complete:
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) Conway’s Game of Life
e) Pokemon Yellow, etc.

10. Which of the following a Non-turing Complete language?
a) Regular Language
b) Context free grammars
c) Epigram
d) All of the mentioned

Answer: There exists some computational languages which are not turing complete. Regular language which is accepted by finite automata tops the list. Other examples are pixel shader languages embedded in Direct3D and OpenGL extensions.