Automata Theory Questions and Answers – Properties-Non Regular Languages

This set of Automata Theory Multiple Choice Questions & Answers focuses on “Properties-Non Regular Languages”.

1. All the regular languages can have one or more of the following descriptions:
i) DFA ii) NFA iii) e-NFA iv) Regular Expressions
Which of the following are correct?
a) i, ii, iv
b) i, ii, iii
c) i, iv
d) i, ii, iii, iv
View Answer

Answer: d
Explanation: The class of languages known as the regular language has atleast four different descriptions: i) DFA ii) NFA iii) e-NFA iv) Regular Expressions

2. Which of the technique can be used to prove that a language is non regular?
a) Ardens theorem
b) Pumping Lemma
c) Ogden’s Lemma
d) None of the mentioned
View Answer

Answer: b
Explanation: We use the powerful technique called Pumping Lemma, for showing certain languages not to be regular. We use Ardens theorem to find out a regular expression out of a finite automaton.

3. Which of the following language regular?
a) {aibi|i>=0}
b) {aibi|0<i<5}
c) {aibi|i>=1}
d) None of the mentioned
View Answer

Answer: b
Explanation: Here, i has limits i.e. the language is finite, contains few elements and can be graphed using a deterministic finite automata. Thus, it is regular. Others can be proved non regular using Pumping lemma.
advertisement
advertisement

4. Which of the following are non regular?
a) The set of strings in {a,b}* with an even number of b’s
b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a
c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0
d) None of the mentioned
View Answer

Answer: d
Explanation: All of the given languages are regular and finite and thus, can be represented using respective deterministic finite automata. We can also use mealy or moore machine to represent remainders for option c.

5. If L is DFA-regular, L’ is
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned
View Answer

Answer: b
Explanation: This is a simple example of a closure property: a property saying that the set of DFA-regular languages is closed under certain operations.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Which of the following options is incorrect?
a) A language L is regular if and only if ~L has finite number of equivalent classes
b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states
c) A language L is NFA-regular if and only if it is DFA-regular
d) None of the mentioned
View Answer

Answer: b
Explanation: Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atleast k states.

7. Myphill Nerode does the following:
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Minimization of DFA and tells us exactly when a language is regular
d) None of the mentioned
View Answer

Answer: c
Explanation: In automata theory, the Myphill Nerode theorem provides a necessary and sufficient condition for a language to be regular. The Myphill Nerode theorem can be used to show a language L is regular by proving that the number of equivalence classes of RL(relation) is finite.
advertisement

8. Which of the following are related to tree automaton?
a) Myphill Nerode Theorem
b) State machine
c) Courcelle’s Theorem
d) All of the mentioned
View Answer

Answer: d
Explanation: The myphill nerode theorem can be generalized to trees and an application of tree automata prove an algorithmic meta theorem about graphs.

9. Given languages:
i) {anbn|n>=0}
ii) <div>n</div>n
iii) {w∈{a,b}∗| #a(w)=#b(w)}, # represents occurrences
Which of the following is/are non regular?
a) i, iii
b) i
c) iii
d) i, ii, iii
View Answer

Answer: d
Explanation: There is no regular expression that can parse HTML documents. Other options are also non-regular as they cannot be drawn into finite automaton.
advertisement

10. Finite state machine are not able to recognize Palindromes because:
a) Finite automata cannot deterministically find the midpoint
b) Finite automata cannot remember arbitarily large amount of data
c) Even if the mid point is known, it cannot find whether the second half matches the first
d) All of the mentioned
View Answer

Answer: d
Explanation: It is the disadvantage or lack of property of a DFA that it cannot remember an arbitrarily such large amount of data which makes it incapable of accepting such languages like palindrome, reversal, etc.

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.