Automata Theory Questions and Answers – Finite Automata-Introduction

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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 View Answer

Answer: d

Explanation: 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 View Answer

Answer: b

Explanation: 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 View Answer

Answer: d

Explanation: Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language. advertisement advertisement 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 View Answer

Answer: d Explanation: 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 View Answer

Answer: b

Explanation: According to the question, minimum of 3 states are required to recognize an octal number divisible by 3. Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 6. Which of the following is not a part of 5-tuple finite automata? a) Input alphabet b) Transition function c) Initial State d) Output Alphabet View Answer

Answer: d

Explanation: 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 View Answer

Answer: a Explanation: A Compiler is used to give a finite solution to an infinite phenomenon. An example of an infinite phenomenon is Language C, etc. advertisement 8. The number of elements in the set for the Language L={xϵ(Σ * Σ) | 'length of x is at most 2'} and Σ={0,1} is _________ a) 7 b) 6 c) 8 d) 5 View Answer

Answer: a

Explanation: Σ 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; View Answer Answer: b Explanation: δ(QXΣ ) = Q1 is the correct representation of change of state. Here, δ is called the Transition function. advertisement 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 View Answer

Answer: b Explanation: Σ * represents any combination of the given set while Σ x represents the set of combinations with length x where x ϵ I.

This is a summation symbol: ∑ or Σ, and here is the Unicode representation: ∑.