Category: Automata Theory Objective Questions

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.

Automata Theory Multiple Choice Questions on “Regular Language & Expression”.

1. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited

Answer:b
Clarification: States, input symbols,initial state,accepting state and transition function.

2. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q

Answer:d
Clarification: Inputs are state and input string output is states.

3. Number of states require to accept string ends with 10.
a) 3
b) 2
c) 1
d) can’t be represented.

Answer:a
Clarification: This is minimal finite automata.

4. Extended transition function is .
a) Q * Σ* -> Q
b) Q * Σ -> Q
c) Q* * Σ* -> Σ
d) Q * Σ -> Σ

Answer:a
Clarification: This takes single state and string of input to produce a state.

5. δ*(q,ya) is equivalent to .
a) δ((q,y),a)
b) δ(δ*(q,y),a)
c) δ(q,ya)
d) independent from δ notation

Answer:b
Clarification: First it parse y string after that it parse a.

6. String X is accepted by finite automata if .
a) δ*(q,x) E A
b) δ(q,x) E A
c) δ*(Q0,x) E A
d) δ(Q0,x) E A

Answer:c
Clarification: If automata starts with starting state and after finite moves if reaches to final step then it called accepted.

7. Languages of a automata is
a) If it is accepted by automata
b) If it halts
c) If automata touch final state in its life time
d) All language are language of automata

Answer:a
Clarification: If a string accepted by automata it is called language of automata.

8. Language of finite automata is.
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Answer:d
Clarification: According to Chomsky classification.

9. Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned

Answer:b
Clarification: Finite automata doesn’t require any stack operation .

10. Number of final state require to accept Φ in minimal finite automata.
a) 1
b) 2
c) 3
d) None of the mentioned

Answer:d
Clarification: No final state requires.

11. Regular expression for all strings starts with ab and ends with bba is.
a) aba*b*bba
b) ab(ab)*bba
c) ab(a+b)*bba
d) All of the mentioned

Answer:c
Clarification: Starts with ab then any number of a or b and ends with bba.

12. How many DFA’s exits with two states over input alphabet {0,1} ?
a) 16
b) 26
c) 32
d) 64

Answer:d
Clarification: Number of DFA’s = 2ⁿ * n^(2*n).

13. The basic limitation of finite automata is that
a) It can’t remember arbitrary large amount of information.
b) It sometimes recognize grammar that are not regular.
c) It sometimes fails to recognize regular grammar.
d) All of the mentioned

Answer:a
Clarification:Because there is no memory associated with automata.

14. Number of states require to simulate a computer with memory capable of storing ‘3’ words each of length ‘8’.
a) 3 * 2⁸
b) 2^(3*8)
c) 2⁽³⁺⁸⁾
d) None of the mentioned

Answer:b
Clarification: 2^(m*n) states requires .

15. FSM with output capability can be used to add two given integer in binary representation. This is
a) True
b) False
c) May be true
d) None of the mentioned

Answer:a
Clarification: Use them as a flip flop output .

Automata Theory Multiple Choice Questions on “Regular Language & Expression”.

1. A regular language over an alphabet a is one that can be obtained from
a) union
b) concatenation
c) kleene
d) All of the mentioned

Answer: d
Clarification: None.

2. Regular expression {0,1} is equivalent to
a) 0 U 1
b) 0 / 1
c) 0 + 1
d) All of the mentioned

Answer: d
Clarification: All are equivalent to union operation.

3. Precedence of regular expression in decreasing order is
a) * , . , +
b) . , * , +
c) . , + , *
d) + , a , *

Answer: a
Clarification: None.

4. Regular expression Φ* is equivalent to
a) ϵ
b) Φ
c) 0
d) 1

Answer: a
Clarification: None.

5. a? is equivalent to
a) a
b) a+Φ
c) a+ϵ
d) wrong expression

Answer: c
Clarification: Zero or one time repetition of previous character .

6. ϵL is equivalent to
a) ϵ
b) Φ
c) L
d) Lϵ

Answer: c,d
Clarification: None.

7. (a+b)* is equivalent to
a) b*a*
b) (a*b*)*
c) a*b*
d) none of the mentioned

Answer: b
Clarification: None.

8. ΦL is equivalent to
a) LΦ
b) Φ
c) L
d) ϵ

Answer: a,b
Clarification: None.

9. Which of the following pair of regular expression are not equivalent?
a) 1(01)* and (10)*1
b) x(xx)* and (xx)*x
c) (ab)* and a*b*
d) x+ and x*x+

Answer: c
Clarification: (ab)*=(a*b*)*.

10. Consider following regular expression
i) (a/b)* ii) (a*/b*)* iii) ((ϵ/a)b*)*
Which of the following statements is correct
a) i,ii are equal and ii,iii are not
b) i,ii are equal and i,iii are not
c) ii,iii are equal and i,ii are not
d) all are equal

Answer: d
Clarification: All are equivalent to (a+b)*.