CompSci 162 Formal Languages and Automata Problem Set 3: Context Free Languages II
Formatting: please start each numbered question on a separate piece of paper, and limit your response to one page. Upload a PDF consisting of these two pages to GradeScope and tag each page. Write in dark ink on light paper, whether you are producing your work digitally or on physical paper. I realize this seems strict, but it really does help with grading, especially with a large class.
Please review the syllabus and course reference for the expectations of assignments in this class. Remember that problem sets are not online treasure hunts. Remember that you may not seek help from any source where not all respondents are subject to UC Irvine’s academic honesty policy.
Please also remember you have a professor and four TAs who want to help you. If you’re lost on this, let us know!
1. Consider the language M = {a n 2 |n ∈ N}. Is M context-free? Justify your answer with either a CFG or PDA (if it is context free) or by using the pumping lemma if it is not.
2. Prove, without using the Pumping Lemma, that the language
L = {w ∈ {a, b, c} ∗ |w has an equal number of a’s, b’s, and c’s, OR some b occurs before some a}
is not context free. You may state and use, without proof, any result from previous practice quizzes, real quizzes, lectures, homework, or reinforcement exercises.