Automata Theory Questions and Answers – Simpler Notations

«
»

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)
L={a, b} | x has a substring ‘aa’ in the production - option a

advertisement

b)
L={a, b} | x has a substring ‘aa’ in the production - option b

c)
L={a, b} | x has a substring ‘aa’ in the production - option c

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

d)
L={a, b} | x has a substring ‘aa’ in the production - option d

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

Answer: d
Explanation: Identity relation: εw = wε = w, thus the one satisfying the given relation will be the identity element.
advertisement

3.Which of the following substring will the following notation result?

The given DFA notation accepts the string of even length & prefix ‘01’
a) 0101011
b) 0101010
c) 010100
d) 100001
View Answer

Answer: c
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

Answer: b
Explanation: Here, δ refers to transition function and results into new state or function when an transition is performed over its state.
advertisement

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}
The tabular representation of DFA is Q1
a) Q0
b) Q1
c) Q2
d) No Transition
View Answer

Answer: b
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.
advertisement

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}
Find the missing transition in the given DFA
a) δ (q0, a) = q0
b) δ (F, a) = q1
c) δ (F, a) = D
d) δ (q1, a) = D
View Answer

Answer: b
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

Answer: c
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

Answer: c
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}
The final state/acceptance state is q2 to the given language
a) q1
b) q2
c) q1, q2
d) q3
View Answer

Answer: b
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}
The final state/acceptance state is q0, q1, q2 to the given language
a) q0, q1
b) q0, q2
c) q1, q2
d) q0, q1, q2
View Answer

Answer: d
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.