Automata Theory Questions and Answers – Regular Language & Expression – 2

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Regular Language & Expression”.

1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11
View Answer

Answer: c
Explanation: string of length 0 = Not possible (because y is always present).
string of length 1 = 1 (y)
string of length 2 = 3 (xy,yy,ya)
string of length 3 = 8 (xxy,xyy,yxy,yyy,yaa,yab,xya,yya)

2. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned
View Answer

Answer: d
Explanation: None.

3. A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine
View Answer

Answer: a
Explanation: All of above machine can accept regular language but all string accepted by machine is regular only for DFA.
advertisement
advertisement

4. Regular grammar is
a) context free grammar
b) non context free grammar
c) english grammar
d) none of the mentioned
View Answer

Answer: a
Explanation: Regular grammar is subset of context free grammar.

5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2
View Answer

Answer: d
Explanation: Finite state machine and regular expression have same power to express a language.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Which of the following is not a regular expression?
a) [(a+b)*-(aa+bb)]*
b) [(0+1)-(0b+a1)*(a+b)]*
c) (01+11+10)*
d) (1+2+0)*(1+2)*
View Answer

Answer: b
Explanation: Except b all are regular expression*.

7. Regular expression are
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
View Answer

Answer: d
Explanation: According to Chomsky hierarchy,
Type 0 – Unrestricted Grammar.
Type 1 – Context Sensitive Grammar.
Type 2 – Context Free Grammar.
Type 3 – Regular Grammar.
advertisement

8. Which of the following is true?
a) Every subset of a regular set is regular
b) Every finite subset of non-regular set is regular
c) The union of two non regular set is not regular
d) Infinite union of finite set is regular
View Answer

Answer: b
Explanation: None.

9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
View Answer

Answer: d
Explanation:If L is recursive enumerable and its complement too if and only if L is recursive.
advertisement

10. Regular expressions are closed under
a) Union
b) Intersection
c) Kleen star
d) All of the mentioned
View Answer

Answer: d
Explanation: According to definition of regular expression.

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.