Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “From PDA to Grammars”.

1. The instantaneous PDA is has the following elements
a) State
b) Unconsumed input
c) Stack content
d) All of the mentioned

Answer: d
Clarification: The instantaneous description of a PDA is represented by 3 tuple:
(q,w,s)
where q is the state, w is the unconsumed input and s is the stack content.

2. The moves in the PDA is technically termed as:
a) Turnstile
b) Shifter
c) Router
d) None of the mentioned

Answer: a
Clarification: A turnstile notation is used for connecting pairs od ID’s taht represents one or many moves of a PDA.

3. Which of the following are the actions that operates on stack top?
a) Pushing
b) Popping
c) Replacing
d) All of the mentioned

Answer: d
Clarification: Push, pop and replace are all the basic and only operations that takes place on stack top.

4. A push down automata is said to be _________ if it has atmost one transition around all configurations.
a) Finite
b) Non regular
c) Non-deterministic
d) Deterministic

Answer: d
Clarification: DPDA or Deterministic Push down automata has atmost one transition applicable to each configuration.

5. Which of the following assertion is false?
a) If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts L by empty stack i.e. L=L(PDA1)=L(PDA2)
b) If L is a CFL then there exists a push down automata P accepting CF; ; by empty stack i.e. L=M(P)
c) Let L is a language accepted by PDA1 then there exist a CFG X such that L(X)=M(P)
d) All of the mentioned

Answer: d
Clarification:
All the assertions mentioned are theorems or corollary.

6. A push down automata can represented using:
a) Transition graph
b) Transition table
c) ID
d) All of the mentioned

Answer: d
Clarification: Yes, a PDA can be represented using a transition diagram, transition table and an instantaneous description.

7. State true or false:
Statement: Every context free grammar can be transformed into an equvalent non deterministic push down automata.
a) true
b) false

Answer: a
Clarification: Push down automata is the automaton machine for all the context free grammar or Type 2 languages.

8. Which of the following statement is false?
a) For non deterministic PDA, equivalence is undecidable
b) For deterministic PDA, equivalence is decidable
c) For deterministic PDA, equivalence is undecidable.
d) None of the mentioned

Answer: c
Clarification: Geraud proved the equivalence problem decidable for Deterministic PDA .

Automata Theory Multiple Choice Questions on “Turing Machine and Halting”.

1. The machine accept the string by entering into hA or it can:
a) explicitly reject x by entering into hR
b) enter into an infinte loop
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: Three things can occur when a string is tested over a turing machine:
a) enter into accept halting state
b) enter into reject halting state
c) goes into loop forever

2. Which of the following can accept even palindrome over {a,b}
a) Push down Automata
b) Turing machine
c) NDFA
d) All of the mentioned

Answer: c
Clarification: A language generating strings which are palindrome is not regular, thus cannot b represented using a finite automaton.

3. Which of the functions can a turing machine not perform?
a) Copying a string
b) Deleting a symbol
c) Accepting a pal
d) Inserting a symbol

Answer: d
Clarification: Different turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and accepting palindromes.

4. If T1 and T2 are two turing machines. The composite can be represented using the expression:
a) T1T2
b) T1 U T2
c) T1 X T2
d) None of the mentioned

Answer: a
Clarification: If T1 and T2 are TMs, with disjoint sets of non halting states and transition function d1 and d2, respectively, we write T1T2 to denote this composite TM.

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