Automata Theory Questions and Answers – Regular Languages and D-PDA

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Regular Languages and D-PDA”.

1. Which of the following is analogous to the following?
:NFA and NPDA
a) Regular language and Context Free language
b) Regular language and Context Sensitive language
c) Context free language and Context Sensitive language
d) None of the mentioned
View Answer

Answer: a
Explanation: All regular languages can be accepted by a non deterministic finite automata and all context free languages can be accepted by a non deterministic push down automata.

2. Let T={p, q, r, s, t}. The number of strings in S* of length 4 such that no symbols can be repeated.
a) 120
b) 625
c) 360
d) 36
View Answer

Answer: b
Explanation: Using the permutation rule, we can calculate that there will be total of 625 permutations on 5 elements taking 4 as the length.

3. Which of the following relates to Chomsky hierarchy?
a) Regular<CFL<CSL<Unrestricted
b) CFL<CSL<Unrestricted<Regular
c) CSL<Unrestricted<CF<Regular
d) None of the mentioned
View Answer

Answer: a
Explanation: The chomsky hierarchy lays down the following order: Regular<CFL<CSL<Unrestricted
advertisement
advertisement

4. A language is accepted by a push down automata if it is:
a) regular
b) context free
c) regular and context free
d) none of the mentioned
View Answer

Answer: c
Explanation: All the regular languages are the subset to context free languages and thus can be accepted using push down automata.

5. Which of the following is an incorrect regular expression identity?
a) R+f=R
b) eR=e
c) Rf=f
d) None of the mentioned
View Answer

Answer: b
Explanation: e is the identity for concatenation. Thus, eR=R.

6. Which of the following strings do not belong the given regular expression?
(a)*(a+cba)
a) aa
b) aaa
c) acba
d) acbacba
View Answer

Answer: d
Explanation: The string acbacba is unacceptable by the regular expression (a)*(a+cba).

7. Which of the following regular expression allows strings on {a,b}* with length n where n is a multiple of 4.
a) (a+b+ab+ba+aa+bb+aba+bab+abab+baba)*
b) (bbbb+aaaa)*
c) ((a+b)(a+b)(a+b)(a+b))*
d) None of the mentioned
View Answer

Answer: c
Explanation: Other mentioned options do not many of the combinations while option c seems most reliable.
advertisement

8. Which of the following strings is not generated by the given grammar:
S->SaSbS|e
a) aabb
b) abab
c) abaabb
d) None of the mentioned
View Answer

Answer: d
Explanation: All the given options are generated by the given grammar. Using the methods of left and right derivations, it is simpler to look for string which a grammar can generate.

9. abb*c denotes which of the following?
a) {abnc|n=0}
b) {abnc|n=1}
c) {anbc|n=0}
d) {abcn|n>0}
View Answer

Answer: b
Explanation: Here, the first mentioned b is fixed while the other can be zero or can be repeated any number of time.
advertisement

10. The following denotion belongs to which type of language:
G=(V, T, P, S)
a) Regular grammar
b) Context free grammar
c) Context Sensitive grammar
d) All of the mentioned
View Answer

Answer: b
Explanation: Ant formal grammar is represented using a 4-tuple definition where V= finite set of variables, T= set of terminal characters, P=set of productions and S= Starting Variable with certain conditions based on the type of formal grammar.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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 & discussions at Telegram SanfoundryClasses.