Computer Science 313
Theory of Computation
Assignment 3 - Chapter 2
Due Wednesday 18 October
Exercises 2.1, 2.4bce, 2.9, 2.14, 2.16. For 2.1, you only
need to show the parse tree.
- Exercise 2.6b. Hint: This is more than just
ambn, m ≠ n. You also need to consider
cases where the a's and b's are out of order. In other words,
this language is
(a ∪ b)* - anbn.
- Write a Chomsky Normal Form context-free grammar class in Python
(or your favorite programming language).
This class should have a constructor method, which takes as inputs the
elements from Definition 2.2 (p. 102):
- A set of variables, implemented as a string of symbols
- A set of terminals, implemented as a string of symbols
- A set of rules, implemented as a list of elements, where each
element contains either three variables (e.g., 'ABC' implementing
A→ BC) or a variable and a terminal
('Aa' implementing A→ a).
Each element can be a tuple, a list, or an object belonging to the class Rule.
- A start symbol, a single character
You should also have an generates method, which takes a string and returns
the grammar generates the string, and returns False otherwise.
This method should implement the algorithm described
Ideally, you should also have
a __repr__ method (takes self and returns a string),
so that printing out a Grammar object will result in
a useful representation (rules with arrows). Put it in a file
cnfgrammar.py along with some test cases and send it as an attachment. I should be able to
run your tests by doing python cnfgrammar.py.