Category: Automata Theory Objective Questions

Automata Theory Multiple Choice Questions on “Epsilon Closures”.

1. Which of the following does not belong to input alphabet if S={a, b}* for any language?
a) a
b) b
c) e
d) none of the mentioned

Answer: c
Clarification: The automaton may be allowed to change its state without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.

2. The number of final states we need as per the given language?
Language L: {an| n is even or divisible by 3}
a) 1
b) 2
c) 3
d) 4
Answer: b

3. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false

Answer: a
Clarification: e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.

4. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.
a) e-NFA
b) Power Construction Method
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: It is more convenient to simulate a machine using e-NFA else the method of Power Construction is used from the union-closure of DFA’s.

Automata Theory online test on “Closure Properties under Boolean Operations”.

1. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be ____________ under an operation op.
a) open
b) closed
c) decidable
d) none of the mentioned

Answer: b
Clarification: If two regular languages are closed under an operation op, then the resultant of the languages over an operation op will also be regular.

2. Suppose a regular language L is closed under the operation halving, then the result would be:
a) 1/4 L will be regular
b) 1/2 L will be regular
c) 1/8 L will be regular
d) Al of the mentioned

Answer: d
Clarification: At first stage 1/2 L will be regular and subsequently, all the options will be regular.

3. If L1′ and L2′ are regular languages, then L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Answer: a
Clarification: Regular language is closed under complement operation. Thus, if L1′ and L2′ are regular so are L1 and L2. And if L1 and L2 are regular so is L1.L2.

4. If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Answer: a
Clarification: If L1 is regular, so is L1′ and if L1′ and L2′ are regular so is L1′ U L2′. Further, regular languages are also closed under intersection operation.

5. If A and B are regular languages, !(A’ U B’) is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Answer: a
Clarification: If A and B are regular languages, then A Ç B is a regular language and A ∩ B is equivalent to !(A’ U B’).

6. Which among the following are the boolean operations that under which regular languages are closed?
a) Union
b) Intersection
c) Complement
d) All of the mentioned

Answer: d
Clarification: Regular languages are closed under the following operations:
a) Regular expression operations
b) Boolean operations
c) Homomorphism
d) Inverse Homomorphism

7. Suppose a language L1 has 2 states and L2 has 2 states. After using the cross product construction method, we have a machine M that accepts L1 ∩ L2. The total number of states in M:
a) 6
b) 4
c) 2
d) 8

Answer: 4
Clarification: M is defined as: (Q, S, d, q0, F)
where Q=Q1*Q2 and F=F1*F2

8. If L is a regular language, then (L’)’ U L will be :
a) L
b) L’
c) f
d) none of the mentioned

Answer: a
Clarification: (L’)’ is equivalent to L and L U L is subsequently equivalent to L.

9. If L is a regular language, then (((L’)r)’)* is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Answer: a
Clarification: If L is regular so is its complement, if L’ is regular so is its reverse, if (L’)^r is regular so is its Kleene.

10. Which among the following is the closure property of a regular language?
a) Emptiness
b) Universality
c) Membership
d) None of the mentioned

Answer: d
Clarification: All the following mentioned are decidability properties of a regular language. The closure properties of a regular language include union, concatenation, intersection, Kleene, complement , reverse and many more operations.

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.