PS4

Computer Science 313
Theory of Computation

Assignment 4 – Chapter 2 (continued)

Due Monday 19 October

  • Look at the Proof Idea for Lemma 2.21 (pp. 115-116), and depict the parsing actions (stack, push, pop) for recognizing the expressions in Exercise 2.1a-d, using the grammar in that exercise. In other words, at each step, show the stack and the input. You can use reasonable abbreviations for the stack and input; for example, E$ is the initial stack, and (a)) represents ((a)) after one input symbol has been consumed.
  • Exercise 2.13. Hint: This is really the union of two languages: the TT part and the U part. There’s no elegant English description of this union, like “binary numbers representing powers of two”. Instead, you’ll have to say “L(G) is the union of two languages: ” and can then give an expression describing each. Now, one part is regular and the other isn’t (it’ll be obvious which is which once you write the expressions). The problem is, it’s possible to have the union of a regular and non-regular language be regular; consider, for example a*b* ∪ anbn, which is just a*b*. Instead, you have to rely on the closure of regular languages under intersection, and come up with another, regular language with which to intersect this big union language. Intersecting with this new regular language should eliminate the regular part of the union, leaving only the non-regular part. Then you can use the Pumping Lemma for regular languages to show that the non-regular part is non-regular.
  • Problem 2.30a

Extra Credit

  • Exercise 2.11

 

  • Use the constructive proof on p. 122 (repeated here) to construct a grammar from the automaton in Figure 2.15 on p. 115, modified to have just q4 as its accepting state, so it no longer accepts the empty string. Just give the rules. Here are some tips:
    • Simplify your variables by leaving out the q in the subscripts; for example, use A23 instead of Aq2q3.
    • First build the rules given by the first part of the construction. The third part can then be used to fill in the missing rule. The second part, which generates a huge number of useless rules in this example, can be ignored. In other words, Just provide the rules necessary to generate the language from the start variable.

 

  • Write a Deterministic Pushdown Automaton class in Python (or your favorite programming language). This class should have a constructor method, which takes as inputs the elements from Definition 2.13 (p. 113), minus the nondeterminism:A set of states, implemented as a list of numbers
    1. An input alphabet, implemented as a string of symbols
    2. A stack alphabet, implemented as a string of symbols
    3. A transition function, implemented as a list of elements, where each element contains a state, an input symbol (no ε’s), a stack symbol, another state, and another stack symbol.
    4. A start state, a single number
    5. A set of accepting states, implemented as a list of numbers.

You should also have an accepts method, which takes a string and returns True if the DPDA accepts the string, and returns False otherwise. Acceptance takes place when the stack is empty and there is no more input, so you don’t have to push and pop the $ symbol. Ideally, you should also have a __repr__ method (takes self and returns a string), so that printing out a DPDA object will result in a useful representation. For the transition function, you can have rules of the form p,a,b –> q,c, where p and q are states and a, b, and c are symbols. For the ε representing stack operations, you can use the symbol @. For example, a DPDA recognizing 0n1n might be represnted as follows:

Q: {q1, q2} Sigma: {0, 1} Gamma: {0} S: q1F: {q2}  delta:   q1,0,@ –> q1,0  q1,1,0 –> q2,@  q2,1,0 –> q2,@

Put your code in a file dpda.py along with some test cases and send it as an attachment. I should be able to run your tests by doing python dpda.py.