This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Simpler Notations”.
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?
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?
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
Explanation: Here, δ refers to transition function and results into new state or function when an transition is performed over its state.
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.
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.
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?
Explanation: Factorial, here is the most appropriate non-infinite domain. Otherwise, palindrome and reverse have infinite domains.
Explanation: According to the given language, q2 Is to become the final/acceptance state in order to satisfy.
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.