COMP 330 Winter 2021 Quiz 4 Solutions
Prakash Panangaden 14th March 2021
Question 1: Which is the only true statement in the following?
1. The pumping lemma for CFL’s can be used to show that a given
language is context-free.
2. The pumping lemma for CFL’s shows that context-free languages are closed under complementation.
3. The pumping lemma for context-free languages only works if one uses a language with a grammar in Chomsky normal form. As this is a very limited subset of the context-free languages, it applies to very few CFL’s.
4. The pumping lemma for CFL’s applies to all CFL’s.
5. The pumping lemma for CFL’s is used to prove that CFL’s are always regular.
Answer 4.
Question 2: What type of language is {anbman|n, m ≥ 0} over the alphabet
{a, b}?
1. Regular but not context free.
2. Neither regular nor context free. 3. Both regular and context-free. 4. It is not a language.
5. Context-free but not regular.
Answer 5.
1
Question 3: What is the only false statement among the following?
1. The language {anbncn|n ≥ 0} is not regular.
2. Any context-free language over a one-letter alphabet is regular.
3. The complement of a deterministic context-free language is always context-free.
4. The intersection of two context-free languages can never be regular.
5. The intersection of a context-free language and a regular language may not be regular.
Answer 4.
Question 4: The language {anbncambm|n, m ≥ 0} is 1. finite.
2. uncountable.
3. regular
4. context-free but not regular.
5. neither context-free nor regular.
Answer 4.
Question 5: Which is the only true statement among the following?
1. A nonregular context-free language cannot contain a subset that is regular and infinite. This follows from the pumping lemma.
2. There are some context-free languages that are finite. This does not violate the pumping lemma.
3. A context-free language must be infinite otherwise pumping would be impossible.
4. A context-free language cannot contain all of Σ∗.
5. A regular language cannot contain a subset that is not even context
free. Answer 2.
2