Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Programming Techniques-Storage and Subroutines”.

1. A turing machine has ____________ number of states in a CPU.
a) finite
b) infinte
c) May be finite
d) None of the mentioned

Answer: a
Clarification: A turing machine has finite number of states in its CPU. However the states are not small in number. Real computer consist of registers which can store values (fixed number of bits).

2. Suppose we have a simple computer with control unit holding a PC with a 32 bit address + Arithmetic unit holding one double length 64 bit Arithmetic Register. The number of states the finite machine will hold:
a) 2^(32*64)
b) 2⁹⁶
c) 96
d) 32

Answer: b
Clarification: According to the statistics of the question, we will have a finite machine with 2^96 states.

3. Which of the following is/are not true for recursively ennumerable language?
a) partially decidable
b) Turing acceptable
c) Turing Recognizable
d) None of the mentioned

Answer: d
Clarification: In automata theory, a formal language is called recursively ennumerable language or partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing machine which will ennumerate all valid strings of the language.

4. According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable language?
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Answer: a
Clarification: Recursively Ennumerable languages are type 0 languages in the Chomsky hierarchy. All regular, context free, context sensitive languages are recursivelyennumerable language.

5. Statement 1: Multitrack Turing machine.
Statement 2: Gamma is Cartesian product of a finite number of finite sets.
Which among the following is the correct option?
a) Statement 1 is the assertion and Statement 2 is the reason
b) Statement 1 is the reason and Statement 2 is the assertion
c) Statement 1 and Statement 2 are independent from each other
d) None of the mentioned

Answer: a
Clarification: Cartesian product works like a struct in C/C++. For Example: Computer tape storage is something like 8 or 9 bits in each cell. One can recognize a multi track tape machine by looking at the transitions because each will have tuples as the read and write symbols.

6. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:
a) input alphabet
b) tape alphabet
c) shift symbols
d) none of the mentioned

Answer: b
Clarification: The 6-tuple (Q, X, S, d, q0, F) can be explained as:
Q represents finite set of states,
X represents the tape alphabet,
S represents the input alphabet
d represents the relation on states and the symbols
q0 represents the initial state
F represents the set of final states.

7. Which of the following statements are false?
a) A multi track turing machine is a special kind of multi tape turing machine
b) 4-heads move independently along 4-tracks in standard 4-tape turing machine
c) In a n-track turing machine, n head reads and writes on all the tracks simultaneously.
d) All of the mentioned

Answer: c
Clarification: In a n-track turing machine, one head reads and writes on all the tracks simultaneously.

8. State true or false:
Statement: Two track turing machine is equivalent to a standard turing machine.
a) true
b) false

Answer: a
Clarification: This can be generalized for n- tracks and can be proved equivalent using ennumerable languages.

Automata Theory Multiple Choice Questions on “Mealy Machine”.

1. In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input

Answer: c
Clarification: Definition of Mealy Machine.

2. Which of the given are correct?
a) Moore machine has 6-tuples
b) Mealy machine has 6-tuples
c) Both Mealy and Moore has 6-tuples
d) None of the mentioned

Answer: c
Clarification: Finite Automaton with Output has a common definition for both the categories.

3. Which one among the following is true?
A mealy machine
a) produces a language
b) produces a grammar
c) can be converted to NFA
d) has less circuit delays

Answer: d
Clarification: It does not produce a language or a grammar or can be converted to a NFA.

4. The O/P of Mealy machine can be represented in the following format:
a) Op(t)= δ(Op(t))
b) Op(t)= δ(Op(t)i(t))
c) Op(t): ∑
d) None of the mentioned

Answer: b
Clarification: The output of mealy machine depends on the present state as well as the input to that state.

5.The ratio of number of input to the number of output in a mealy machine can be given as:
a) 1
b) n: n+1
c) n+1: n
d) None of the mentioned

Answer: a
Clarification: The number of output here follows the transitions in place of states as in Moore machine.

6. Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata

Answer: b
Clarification: They are collectively known as Transducers.

7. The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned

Answer: a
Clarification: Mealy and Moore machine vary over how the outputs depends on prior one (transitions) and on the latter one(states).

8. Statement 1: Mealy machine reacts faster to inputs.
Statement 2: Moore machine has more circuit delays.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true but Statement 2 is false
c) Statement 1 is false and Statement 2 is true
d) None of the mentioned is true

Answer: a
Clarification: Being an input dependent and output capable FSM, Mealy machine reacts faster to inputs.

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

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

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

Answer: d
Clarification: 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)⁴
b) (0+1)⁴
c) (01)⁴
d) (0+1+ε)⁴

Answer: d
Clarification: The extended notation would be (0+1)⁴ 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}

Answer: a
Clarification: The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.

6. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct

Answer: b
Clarification: Two operands are said to be performing Concatenation operation AB = A•B = {xy: x ∈ A & y ∈ B}.

7. Concatenation of R with Ф outputs:
a) R
b) Ф
c) R.Ф
d) None of the mentioned

Answer: b
Clarification: By distributive property (Regular expression identities), we can prove the given identity to be Ф.

8. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R

Answer: a
Clarification: RR*=R+ as R+ means the occurrence to be at least once.

Automata Theory online quiz on “Conversions among Representations”.

1. Which of the following conversion is not feasible?
a) Regular expression to automaton conversion
b) Automaton to Regular Expression Conversion
c) NFA to DFA
d) None of the mentioned

Answer: d
Clarification: Each of the four formats of representation of the regular language be it, DFA, NFA, Regular Expression or e-NFA can be converted to the rest three forms.

2. The computation of e-closure of n-states takes ______ time.
a) O(n²)
b) O(n³)
c) O(2ⁿ)
d) None of the mentioned

Answer: b
Clarification: We must search from each of the n states along all arcs labelled e. If there are n states, there can be no more than n² states.

3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).
a) n
b) n^1/2
c) n²
d) 2ⁿ

Answer: a
Clarification: The conversion DFA to NFA is simple, and takes O(n) time on an n-state DFA.

4. With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n is the number of states of DFA, we can _________ the size of the regular expression constructed.
a) double
b) triple
c) quadruple
d) none of the mentioned

Answer: c
Clarification: We can quadruple the size of the regular expression per round. Thus, we can simply write n³ expressions can take time O(n³4ⁿ), where n =number of states of the DFA.

5. Conversion of regular expression to e-NFA takes ___________ time.
a) linear
b) exponential
c) logarithmic
d) none of the mentioned

Answer: a
Clarification: It is possible to parse the expression efficiently, using a technique that takes only O(n) time on a expression of length n³.

6. The conversion of NFA to DFA can be done in:
a) exponential time
b) linear time
c) logarithmic time
d) all of the mentioned

Answer: a
Clarification: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n³) time, without changing the number of states.Next, producing to DFA can take exponential time.

7. Which of the following cannot be converted in an ordinary NFA?
a) DFA
b) Regular Expression
c) e-NFA
d) None of the mentioned

Answer: d
Clarification: Each of the following can expressed in terms of ordinary NFA with different time complexities.

8. NFA to DFA conversion is done via
a) Subset Construction method
b) Warshalls Algorithm
c) Ardens theorem
d) None of the mentioned

Answer: a
Clarification: Powerset or subset construction method is a standard method for converting a non deterministic finite automata into DFA which recognizes the same formal language.

9. State true or false:
Statement: Regular expression can directly be converted to DFA without intermediate steps.
a) true
b) false

Answer: b
Clarification: There exists subsequent steps like formation of epsilon-NFA and NFA before the formation of corresponding DFA.

10. Is the following statement correct?
Statement: Thompson construction is used to convert Regular expression to finite automata.
a) Yes
b) No

Answer: a
Clarification: Thompson’s Construction is used to find out a Finite Automaton from a Regular Expression. We will reduce the regular expression into smallest regular expressions and convert them to NFA and finally to DFA.

Automata Theory Multiple Choice Questions on “Regular Languages and D-PDA”.

1. Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned

Answer: a
Clarification: All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.

2. Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.
a) 120
b) 625
c) 360
d) 36

Answer: b
Clarification: Using the permutation rule, we can calculate that there will be total of 625 permutations on 5 elements taking 4 as the length.

3. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned

Answer: a
Clarification: The chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted

4. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) both (a) and (b)
d) none of the mentioned

Answer: c
Clarification: All the regular languages are the subset to context free languages and thus can be accepted using push down automata.

5. Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned

Answer: b
Clarification: e is the identity for concatenation. Thus, eR=R.

6. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba

Answer: d
Clarification: The string acbacba is unacceptable by the regular expression (a)*(a+cba).

7. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) ((a+b)(a+b)(a+b)(a+b))*
d) None of the mentioned

Answer: c
Clarification: Other mentioned options do not many of the combinations while option c seems most reliable.

8. Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned

Answer: d
Clarification: All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.

9. abb*c denotes which of the following?
a) {abnc|n=0}
b) {abnc|n=1}
c) {anbc|n=0}
d) {abcn|n>0}

Answer: b
Clarification: Here, the first mentioned b is fixed while the other can be zero or can be repeated any number of time.

10. The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned

Answer: b
Clarification: Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar.

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

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

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

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

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

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

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

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

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

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

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