Automata Theory Multiple Choice Questions on “Finite Automata-Introduction”.
1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive
Answer: d
Clarification: A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.
2. The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1
a) 01,0011,010101
b) 0011,11001100
c) ε,0011,11001100
d) ε,0011,11001100
Answer: b
Clarification: The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.
3. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned
Answer: d
Clarification: Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.
4. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be its states; Statement 3: The edges or arcs can be used for transitions
Hint: Nodes and Edges are for trees and forests too.
Which of the following make the correct combination?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned
Answer: d
Clarification: It is possible to represent a finite automaton graphically, with nodes for states, and arcs for transitions.
5. The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1
b) 3
c) 5
d) 7
Answer: b
Clarification: According to the question, minimum of 3 states are required to recognize an octal number divisible by 3.
6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
Answer: d
Clarification: A FA can be represented as FA= (Q, ∑, δ, q0, F) where Q=Finite Set of States, ∑=Finite Input Alphabet, δ=Transition Function, q0=Initial State, F=Final/Acceptance State).
7. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________
a) Compiler
b) Interpreter
c) Loader and Linkers
d) None of the mentioned
Answer: a
Clarification: A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.
8. The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is_________
a) 7
b) 6
c) 8
d) 5
Answer: a
Clarification: ∑r= {1,0} and a Kleene* operation would lead to the following set=COUNT{ε,0,1,00,11,01,10} =7.
9. For the following change of state in FA, which of the following codes is an incorrect option?
a) δ (m, 1) =n
b) δ (0, n) =m
c) δ (m,0) =ε
d) s: accept = false; cin >> char;
if char = “0” goto n;
Answer: b
Clarification: δ(QX∑) = Q1 is the correct representation of change of state. Here, δ is called the Transition function.
10. Given: ∑= {a, b}
L= {xϵ∑*|x is a string combination}
∑4 represents which among the following?
a) {aa, ab, ba, bb}
b) {aaaa, abab, ε, abaa, aabb}
c) {aaa, aab, aba, bbb}
d) All of the mentioned
Answer: b
Clarification: ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x ϵ I.