SI342: Python - Playing with DFAs

DFAs - relaxing the rules

Our goal is write code that takes a 5-tuple representing a DFA and runs that DFA on input strings. To make writing down the 5-tuples easier for users, we will modify the rules a bit. Here's how:

We will represent transitions as a set of triples, just like we normally do for NDFAs, but $\lambda$-transitions and multiple outgoing transitions for the same symbol from the same state are not allowed. However ...
Missing transitions are allowed. If we are in state $q$ with symbol $x$ to read and there is no outgoing transition from $q$ for $x$, the input is rejected.

With these minor modifications in place, we can represent DFAs with python tuples and sets super easily. Here are two examples, which we will use. One important thing to notice is that the set of states and of symbols can accommodate many different types - they are not limited to just being strings!

One way to implement a DFA

Below I've given a simple class with a constructor that takes a DFA description (as described above) and method run(·) that takes a sequence of symbols from the machine's alphabet and runs the machine on that input, returning True if the input is accepted and False otherwise. Along with the code are a few sample runs.

$ python3 -i dfa.py
>>> from ex0 import M0
>>> M = DFA(M0)
>>> M.run("abaabc")
True
>>> from ex1 import M1
>>> Mp = DFA(M1)
>>> Mp.run([6,4,6,8])
True

Here's an example of unpacking a 3-tuple.

>>> a,b,c = (2*5+1,"foobar",{'a','b'})
>>> a
11
>>> b
'foobar'
>>> c
{'b', 'a'}

Note: The first line of the constructor makes use of "unpacking", which is a cute python feature. If you have a list or tuple on the right-hand side of an assignment, on the left you can put a comma-separated list of variable names, and the list/tuple values are unpacked and assigned individually, in order, to the variables. There's an example in the box to the right.

TODO

Create the three files ex0.py, ex1.py and dfa.py, and find inputs that M0 and M1 reject, and inputs that they accept that are different from the above examples.
Explain what Tmap is, and how the heck it works!
How is it possible that both calls to run work in he example below, even though one uses a string and the other a list?
```
>>> from ex0 import M0
>>> M = DFA(M0)
>>> M.run("abaabc")
True
>>> M.run(['a','b','a','a','b','c'])
True
```
In what situation is False returned because of the KeyError exception? Find an input to give run that causes the KeyError exception. (You might want to add a temporary print or something to make sure that you really are causing a KeyError exception.)

Show me the running

Take my DFA code and add a method "showrun" that acts just like run, except that it prints out a representation of the computation in the form shown below.
Note: Obviously it would be more in keeping with the way we work with computations to show sequences of configurations, but this way is a bit more compact and easier to look at on-screen.

Important! To tell print not to stick a newline at the end, call it like: print("blah",end="")

>>> from ex0 import M0
>>> M = DFA(M0)
>>> M.showrun("abaabc") 
q1 =a=> q2 =b=> q2 =a=> q1 =a=> q2 =b=> q2 =c=> q3 
True
>>> M.showrun("ac")
q1 =a=> q2 =c=> q3
True

>>> from ex1 import M1
>>> Mp = DFA(M1)
>>> Mp.showrun([6,4,6,8]) 
1 =6=> 1 =4=> 2 =6=> 2 =8=> 3 
True

Pump up the jam

Add to the DFA class a method plv2, which takes an input just like run, but which returns three values (literally just return three comma-separated values) that are strings x, y and z from the pumping lemma version 2.0. You may assume the input is accepted by the machine.

>>> from ex0 import M0
>>> M = DFA(M0)
>>> M.showrun("abaabc")
q1 =a=> q2 =b=> q2 =a=> q1 =a=> q2 =b=> q2 =c=> q3
True
>>> x,y,z = M.plv2("abaabc")
>>> f"x = {x}, y = {y}, z = {z}"
'x = a, y = b, z = aabc'

Here's another example input. The line:

>>> Mx = ({0,1,2},{'b','a'},{(1,'b',0),(1,'a',2),(2,'a',0),(2,'b',1),(0,'a',1),(0,'b',2)},0,{0})

... defines the machine:

>>> M0 = DFA(Mx)
>>> M0.showrun("bbaaab")
0 =b=> 2 =b=> 1 =a=> 2 =a=> 0 =a=> 1 =b=> 0
True
>>> M0.plv2("bbaaab")
('b', 'ba', 'aab')
>>> M0.showrun("babaab")
0 =b=> 2 =a=> 0 =b=> 2 =a=> 0 =a=> 1 =b=> 0
True
>>> M0.plv2("babaab")
('', 'ba', 'baab')

Important!

I added a counter to count how many symbols I had read so far, and I added a map M that mapped a state to the counter value from when I first encountered that state. When I moved to state q, I checked whether q was already a key in the map (q in M). If so, I found a loop in the computation, and I could use the counter values to figure out the substring ranges for x, y and z.
This is superhelpful: If w is a string, and i and j are integer indices, w[i:j] is the substring $w_iw_{i+1}\cdots w_{j-1}$. Also, w[:j] is short for "w[0:j]", and w[i:] is short for "w[i:n]", where $n$ is the length of $w$. These are called "slices". They work exactly the same way for lists!
```
>>> s = "beatarmy"
>>> s[1:4]
'eat'
>>> s[:4]
'beat'
>>> s[4:]
'army'
```

One last thing ...

It would be nice if you would define your own exception class, PLException, and throw it if someone calls plv2 on an input string that is not accepted.