This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Simpler Notations”.
1.Given Language: L= {xϵ∑= {a, b} |x has a substring ‘aa’ in the production}. Which of the corresponding representation notate the same?
a)
b)
c)
d)
Explanation: The states transited has been written corresponding to the transitions as per the row and column. The row represents the transitions made and the ultimate.
2.Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information what is the identity element for the string?
a) u-1
b) v-1
c) u-1v-1
d) ε
View Answer
Explanation: Identity relation: εw = wε = w, thus the one satisfying the given relation will be the identity element.
3.Which of the following substring will the following notation result?
a) 0101011
b) 0101010
c) 010100
d) 100001
View Answer
Explanation: The given DFA notation accepts the string of even length and prefix ‘01’.
4.Predict the following step in the given bunch of steps which accepts a strings which is of even length and has a prefix=’01’
δ (q0, ε) =q0 < δ(q0,0) =δ (δ (q0, ε),0) = δ(q0,0) =q1 < _______________
a) δ (q0, 011) =δ (δ (q0,1), 1) =δ (q2, 1) =q3
b) δ (q0, 01) =δ (δ (q0, 0), 1) = δ (q1, 1) =q2
c) δ (q0, 011) =δ (δ (q01, 1), 1) =δ (q2, 0) =q3
d) δ (q0, 0111) =δ (δ (q0, 011), 0) = δ (q3, 1) =q2
View Answer
Explanation: Here, δ refers to transition function and results into new state or function when an transition is performed over its state.
5. Fill the missing blank in the given Transition Table:
Language L= {xϵ∑= {0,1} |x accepts all the binary strings not divisible by 3}
a) Q0
b) Q1
c) Q2
d) No Transition
View Answer
Explanation: The tabular representation of DFA is quite readable and can be used to some ore complex problems. Here, we need to form the transition graph and fill up the given blank.
6. Which among the following is the missing transition in the given DFA?
L= {xϵ∑= {a, b} | x starts with a and ends with b}
a) δ (q0, a) = q0
b) δ (F, a) = q1
c) δ (F, a) = D
d) δ (q1, a) = D
View Answer
Explanation: For the given Language, the transition missing is δ (F, a) = q1.
7. The complement of a language will only be defined when and only when the __________ over the language is defined.
a) String
b) Word
c) Alphabet
d) Grammar
View Answer
Explanation: It is not possible to define the complement of a language without defining the input alphabets. Example: A language which does not consist of substring ‘ab’ while the complement would be the language which does contain a substring ‘ab’.
8. Which among the following is not notated as infinite language?
a) Palindrome
b) Reverse
c) Factorial
d) L={ab}*
View Answer
Explanation: Factorial, here is the most appropriate non-infinite domain. Otherwise, palindrome and reverse have infinite domains.
9. Which among the following states would be notated as the final state/acceptance state?
L= {xϵ∑= {a, b} | length of x is 2}
a) q1
b) q2
c) q1, q2
d) q3
View Answer
Explanation: According to the given language, q2 Is to become the final/acceptance state in order to satisfy.
10. Which of the following are the final states in the given DFA according to the Language given.?
L= {xϵ∑= {a, b} |length of x is at most 2}
a) q0, q1
b) q0, q2
c) q1, q2
d) q0, q1, q2
View Answer
Explanation: According to the given language, the length is at most 2, thus the answer is found accordingly.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Automata Theory Books
