Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Moore Machine”.

1. Moore Machine is an application of:
a) Finite automata without input
b) Finite automata with output
c) Non- Finite automata with output
d) None of the mentioned

Answer: b
Clarification: Finite automaton with an output is categorize din two parts: Moore M/C and Mealy M/C.

2. In Moore machine, output is produced over the change of:
a) transitions
b) states
c) Both
d) None of the mentioned

Answer: b
Clarification: Moore machine produces an output over the change of transition states while mealy machine does it so for transitions itself.

3. For a give Moore Machine, Given Input=’101010’, thus the output would be of length:
a) |Input|+1
b) |Input|
c) |Input-1|
d) Cannot be predicted

Answer: a
Clarification: Initial state, from which the operations begin is also initialized with a value.

4. Statement 1: Null string is accepted in Moore Machine.
Statement 2: There are more than 5-Tuples in the definition of Moore Machine.

Choose the correct option:
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true while Statement 2 is false
c) Statement 1 is false while Statement 2 is true
d) Statement 1 and Statement 2, both are false

Answer: a
Clarification: Even ε, when passed as an input to Moore machine produces an output.

5. The total number of states and transitions required to form a moore machine that will produce residue mod 3.
a) 3 and 6
b) 3 and 5
c) 2 and 4
d) 2 and 5
Answer: a

6. Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned

Answer: a
Clarification: Statement a and b is correct while c is false. Finite machines with output have no accepting states and can be converted within each other.

7. What is the output for the given language?
Language: A set of strings over ∑= {a, b} is taken as input and it prints 1 as an output “for every occurrence of a, b as its substring. (INPUT: abaaab)
a) 0010001
b) 0101010
c) 0111010
d) 0010000

Answer: a
Clarification: The outputs are as per the input, produced.

8. The output alphabet can be represented as:
a) δ
b) ∆
c) ∑
d) None of the mentioned

Answer: b
Clarification: Source-The tuple definition of Moore and mealy machine comprises one new member i.e. output alphabet as these are finite machines with output.

9. The O/P of Moore 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: a
Clarification: Op(t)=δ(Op(t)) is the defined definition of how the output is received on giving a specific input to Moore machine.

Automata Theory Multiple Choice Questions on “Union, intersection and complement of Regular Language & Expression”.

1. Regular sets are closed under union,concatenation and kleene closure.
a) True
b) False
c) Depends on regular set
d) Can’t say

Answer:a
Clarification: Regular sets are closed under these three operation.

2. Complement of a DFA can be obtained by
a) making starting state as final state.
b) no trival method.
c) making final states non-final and non-final to final.
d) make final as a starting state.

Answer:c
Clarification: String accepted in previous DFA will not be accepted and non accepting string will be accepted .

3. Complement of regular sets are _________
a) Regular
b) CFG
c) CSG
d) RE

Answer:a
Clarification: Regular sets are closed under complement operation.

4. If L1 and L2 are regular sets then intersection of these two will be
a) Regular
b) Non Regular
c) Recursive
d) Non Recursive

Answer:a
Clarification: Regular expression are also colsed under intersection.

5. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be
a) Empty set
b) CFG
c) Decidable
d) Regular

Answer:d
Clarification: Regular is closed under difference.

6. Reverse of a DFA can be formed by
a) using PDA
b) making final state as non-final
c) making final as starting state and starting state as final state
d) None of the mentioned

Answer:c
Clarification: By making final state as starting state string starting from end will be accepted.

7. Reverse of (0+1)* will be
a) Phi
b) Null
c) (0+1)*
d) (0+1)

Answer:c
Clarification: There is only one state which is start and final state of DFA so interchanging starting start and final state doesn’t change DFA.

8. A ___________ is a substitution such that h(a) contains a string for each a.
a) Closure
b) Interchange
c) Homomorphism
d) Inverse Homomorphism

Answer:c
Clarification: This operation replace using a function .

9. Homomorphism of a regular set is _______
a) Universal set
b) Null set
c) Regular set
d) Non regular set

Answer:c
Clarification: Regular set are closed under homomorphism.

10. (a ^ 5b ^ 5)* is example of ________
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language

Answer:d
Clarification: It is a regular expression.

11. Which of the following is type 3 language ?
a) Strings of 0’s whose length is perfect square
b) Palindromes string
c) Strings of 0’s having length prime number
d) String of odd number of 0’s

Answer:d
Clarification: Only d is regular language.

12. a ^ nb ^ n where (n+m) is even .
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Answer:d
Clarification: It is a regular expression.

13. Complement of a ^ nb ^ m where n >= 4 and m <= 3 is example of
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Answer:d
Clarification: It is a regular expression.

14. a ^ nb ^ m where n >= 1, m >= 1, nm >= 3 is example of
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Answer:d
Clarification: It is a regular expression.

15. Complement of (a + b)* will be
a) phi
b) null
c) a
d) b

Answer:a
Clarification: Given expression accept all string so complement will accept nothing.

Automata Theory Multiple Choice Questions on “Reversal-Homomorphism and Inverse Homomorphism”.

1. If L is a language, the reversal of the language can be represented as:
a) L’
b) L^c
c) L^r
d) more than one option is correct

Answer: c
Clarification: L^r is defined as the reversal of a language. L^r is a set of strings whose reversal is in L.
Example: L={0, 01, 100}
Lr={0, 10, 001}

2. If L is a regular language, ____ is also regular.
a) L^r
b) L’
c) L*
d) All of the mentioned

Answer: d
Clarification: L^r, L’, L* i.e. reversal, complementation and kleene all are the closure properties of regular language.

3. If E=F+G;
E^r=?
a) F^r+G^r
b) (F+G)^r
c) Both (a) and (b)
d) None of the mentioned

Answer: a
Clarification: If E is a symbol a, e, or f, then Er=E. Other inductive properties include union of reversals, concatenation and Kleene.

4. If E= FG, E^r=?
a) F^rG^r
b) G^rF^r
c) Both (a) and (b)
d) None of the mentioned

Answer: b
Clarification: If E= FG, E^r=G^rF^r . Example: (01*)R=(1*)R(0)R

5. Simplify the following identity:
E=01*+10*
E^R=?
a) (1*0+0*1)
b) (01*10*)^R
c) (0*1+10*)
d) All of the mentioned

Answer: a
Clarification: 01*+10*
ER=(01*)^R+(10*)^R=>(1*)^R0^R+(0*)^R1^R=>1*0+0*1

6. Which of the following obey the closure properties of Regular language?
a) Homomorphism
b) Inverse Homomorphism
c) Reversal
d) All of the mentioned

Answer: d
Clarification: Homomorphism on an aphabet is a function that gives a string for each symbol in that alphabet. Example: h(0)=ab, etc.

7. Let h(L) be a language of regular expression abe*+e(ab)*. Simplify the h(L)
a) (ab)*+eab*
b) abe*+ea*b*
c) (ab)*
d) None of the mentioned

Answer:
abe*+e(ab)*(Using the identities e=e*, eE=Ee=E)
=ab+(ab)*=> ab will contain inside (ab)*, thus =>(ab)*.

8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)=_______
a) the language of two one’s and any number of zeroes
b) the language of two zeroes and any number of one’s
c) the language of two zeroes and two one’s
d) none of the mentioned

Answer: b
Clarification: h-1(L) is the language with two 0’s and any number of 1’s=>(1*01*01*).

9. While proving Inverse Homomorphism, which of the following steps are needed?
a) Start with a DFA Ain L
b) Construct a DFA B for h-1(L)
c) The set of states, initial and final states should be same.
d) All of the mentioned

Answer: d
Clarification: While constructing DFA B, we need to take care of the following:
a) The same set of states
b) The same start state
c) The same final state
d) Input alphabet = the symbols to which homomorphism h applies.

10. 8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)= the language of two zeroes and any number of one’s.
The given example belongs to which of the following?
a) Homomorphism
b) Inverse Homomorphism
c) Both (a) and (b)
d) None of the mentioned

Answer: b
Clarification: Let h be a homomorphism and L a language whose alphabet is the output language of h.
h-1(L) = {w | h(w) is in L}.

Automata Theory Multiple Choice Questions on “Deterministic PDA”

1. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned

Answer: a
Clarification: A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.

2. A PDA machine configuration (p, w, y) can be correctly represented as:
a) (current state, unprocessed input, stack content)
b) (unprocessed input, stack content, current state)
c) (current state, stack content, unprocessed input)
d) none of the mentioned

Answer: a
Clarification: A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).

3. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned

Answer: b
Clarification: A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)

4. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned

Answer: d
Clarification: The empty stack in the end is our requirement relative to finite state automatons.

5. A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned

Answer: a
Clarification: A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.

6. State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
a) true
b) false

Answer: a
Clarification: There exists two lemma’s such that:
a) Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence

7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
d) none of the mentioned

Answer: a
Clarification: To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M, by both acceptance criteria.

8. A language accepted by Deterministic Push down automata is closed under which of the following?
a) Complement
b) Union
c) Both (a) and (b)
d) None of the mentioned

Answer: a
Clarification: Deterministic Context free languages(one accepted by PDA by final state), are drastically different from the context free languages. For example they are closed under complementation and not union.

9. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned

Answer: a
Clarification: JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.

10. Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned

Answer: a
Clarification: The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.

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.