Lectures, Assignments, and Exercises
2.1 dfa
2.2 nfa
2.3 re
2.4 cfl
2.5 tms
2.6 vtms
2.7 dec
2.8 undec
2.9 Paper
2.10 Presentation
2.11 Midterm
2.12 Final

2.4 cfl

This exercise is optional. Refer to the exercise policy for details.
Do the exercises in sections 2.1 and 2.2 in the textbook.
Implement an interpreter for CFGs that takes their tuple representation and can generate strings from the language. I suggest implementing a mode that randomly generates one string and another version that generates all strings up to some depth.
Implement a compiler from general CFGs to CFGs in Chomsky normal form.
Implement a compiler from CFGs to PDAs.
Implement an interpreter for PDAs that takes their tuple representation and a string, then returns whether the string is accepted or not.
Implement a compiler from PDAs to CFGs.