PS3

Computer Science 313
Theory of Computation

Assignment 3 – Chapter 2

Due Monday 5 October

Exercises 2.1, 2.4bce, 2.9, 2.14, 2.16. For 2.1, you only need to show the parse tree.

Extra Credit

  • 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):
    1. A set of variables, implemented as a string of symbols
    2. A set of terminals, implemented as a string of symbols
    3. 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.
    4. A start symbol, a single character

    You should also have an generates method, which takes a string and returns True if the grammar generates the string, and returns False otherwise. This method should implement the algorithm described here. 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.