COMP 330 Winter 2021 Quiz 3 Solutions
Prakash Panangaden 2nd March 2021
Question 1: Which is the only true statement of the following? 1. Context-free languages have to be finite.
2. Every regular language is context-free.
3. A language cannot be both regular and context-free.
4. Every language is either regular or context-free.
5. Every context-free language is regular. Answer 2.
Question 2: What type of language is {anbn|n ¡Ý 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.
Question 3: What is the only false statement among the following? 1. The language {anbncn|n ¡Ý 0} is not context-free.
2. Any finite language is context free.
1
3. The intersection of a context-free language and a regular language is always context-free.
4. The intersection of two context-free languages can never be context free.
5. The intersection of two context-free languages may not be context free.
Answer 4.
Question 4: The language {ai+jbj+kck+ldi+l|i,j,k,l ¡Ý 0} over the alphabet {a,b,c,d} is
1. not properly defined.
2. regular.
3. finite.
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 context-free language cannot contain a subset that is regular.
2. There are some context-free languages that contain no infinite regular subsets.
3. A context-free language must contain an infinite regular subset.
4. A context-free language cannot contain a finite subset.
5. A regular language cannot contain a subset that is context free.
Answer 2.
2