Instructions
This problem set is due on Wednesday February 19, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.
Problems
- Prove that the context-free languages are closed under the regular operations (union, concatenation, star). That is, given two context-free grammars $G_1$ and $G_2$, show how to construct a context-free grammar for each of $L(G_1) \cup L(G_2)$, $L(G_1) L(G_2)$, and $L(G_1)^*$.
- A grammar $G = (V,\Sigma,P,S)$ is a right-linear grammar if all productions in $P$ are of the form
- $A \rightarrow aB$, where $A,B \in V$ are variables and $a \in \Sigma$ is a terminal symbol,
- $A \rightarrow \varepsilon$, where $A \in V$ is a variable.
In other words, the right hand side of productions are restricted to a single terminal symbol followed by a single variable, or exactly the empty string $\varepsilon$.
- Show that if $L$ is a regular language, then there is a right linear grammar that generates it.
- We can also define left linear grammars in a similar way, where productions are of the form $A \rightarrow Ba$. One can show that these also generate regular languages. However, linear grammars are grammars that can contain both left and right linear production rules, and linear grammars can generate languages that are not regular.
Give a linear grammar that generates a non-regular language. Explain informally how your grammar generates the language and how the language is not regular (for example: we proved this language is not regular before in class, closure properties argument, quick and dirty pumping or Myhill-Nerode argument).
- Consider the language
$$L = \{a^i b^j c^k \mid i + j \geq k; i,j,k \geq 0\},$$ over the alphabet $\{a,b,c\}$.
- Give a context-free grammar for $L$ (i.e., list its productions) and explain informally how your grammar generates $L$.
- Convert your grammar into Chomsky Normal Form.
- Give the final CYK table for the word $aaabcc$ on your CNF grammar from (b).
Reflection
Once in a while, there will be a reflection section attached to a problem set. These are meant to give you an opportunity to reflect on your relationship with the course and the things you're learning. I will be reading and responding to your submissions, so this will also allow us to establish a dialogue about your learning in this course.
Completion of this part is optional but is worth an extra 10 marks in total. These will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness".
- What has been your favourite result so far?
- What is something that you've learned or improved on since this class started?
- Think back to your goals for this class. How do you feel about your progress? Do you need to revise them? What do you think you would need to work on to meet them?
- Is there anything else you would like me to know at this point?