TOC UNIT 2B

Which language is generated by the regular expression (a|b)abb?

• Strings ending in abb

• Strings containing abb

• Strings starting with abb

• All strings over {a, b}

Which of the following is NOT a regular language?

• {aⁿbⁿ | n ≥ 0}

• {a, ab, abb, abbb, …}

• {w | w contains an even number of 0s}

• {w | w does not contain the substring '11'}

Which of the following is TRUE about regular expressions and finite automata?

• Every regular expression can be converted to an NFA

• Every DFA has a corresponding regular expression

• They both define regular languages

• All of the above

Which of these operations preserve regularity?

• Union

• Concatenation

• Kleene star

• All of the above

Pumping Lemma is used to:

• Convert NFA to DFA

• Prove a language is regular

• Prove a language is not regular

• Minimize a DFA

Which of the following is NOT closed under regular languages?

• Union

• Intersection

• Complement

• Context-Free Grammar

If L1 and L2 are regular, then L1 ∩ L2 is:

• Always regular

• Never regular

• Regular only if L1 ⊆ L2

• Not guaranteed to be regular

Let L = {aⁿbⁿ | n ≥ 0}. Can we use Pumping Lemma to prove L is not regular?

• No, because L is regular

• Yes, because it fails the Pumping Lemma

• No, because L is context-free

• Yes, because it satisfies the Pumping Lemma

Which of the following languages is regular?

• {aⁿbⁿ | n ≥ 1}

• {w | w is a palindrome}

• {aⁿ | n is even}

• {w | w = w^R}

What does the Pumping Lemma guarantee for a regular language L?

• Every string can be written as xyz with |xy| ≤ p

• Every substring y can be removed

• There exists a string that cannot be pumped

• All strings must be of length p