CompSci 162 Formal Languages and Automata Problem Set 2: Context Free Languages I
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. Give a CFG for the following language over the alphabet Σ = {a, b}: {a n b kubka n : n, k ≥ 1, u ∈ Σ ∗}. Do this by creating the CFG directly; do not do this by creating a PDA and converting it to a CFG.
2. Give a PDA that accepts the language {a n b k c n+k : n ≥ 0, k ≥ 0}. Do this by creating the PDA directly; do not do this by creating a CFG and converting it to a PDA.