No Lambda Transitions

Let's start with the case of no λ transitions, as that will be easier to handle, and it matches the formal definition we gave for NFAs. Code is shown below:

This code is quite similar to the DFA evaluation code we wrote, except the state transitions map onto a set of states. Likewise, we keep track of a set of states during the evaluation of the machine to keep track of the unique parallel universes we're considering. Finally, we accept if at least one state is in the set of accept states F.

As an example, let's return to the NFA that accepts strings that have a 1 in the 2's place:

If we evaluate it

then it prints the following:

This matches the picture we drew

---

Reducing Lambda Transitions

The above code is useful for the textbook definition of NFAs, but as we've seen, adding λ transitions can make it much easier to specify certain NFAs, and this will be crucial for us on the next assignment when we create grep⁽¹⁾

First, let's talk about how to represent λ transitions in python. Let's start with the union example from before. We'll use python None to represent λ, as shown below

Now, rather than rewriting our code to evaluate NFAs, we'll do the reduction from NFAs with λ to those without so we can use the evaluation code we already have. First, we'll create a helper method to figure out which states are reachable from a particular state via a sequence of λ transitions. To accomplish this, we'll use depth-first graph search:

Let's look at the crazy example we had from before:, but we'll add one more λ transition from q3 to q1 to create a cycle, just to make sure we can handle that

If we check the method we just made on all the states

then we get this:

which is correct. Let's finish the reduction now by adding non-lambda arrows out of the reachable states to each state, and by updating the accept states

Let's run this code on the example we have and see what we get:

The new transitions and new accept states are depicted in red. We've added lots of arrows, but it seems our code has worked correctly! This is a useless example in practice since every state accepts (since every state can reach q2 with a sequence of λ transitions), but it was good to test our code on

Union Example Again

Now let's go back to the union example and see what we get:

And we get

This accepts because even though in one of the unique parallel universes it ends on q2, in the other one, it ends on podd, an accept state

Messy Lambda Clone Example

Finally, let's go back and look at this example

We get the output below, which matches the picture we drew before on the right; that is, we end up in state q1, which is adjacent to q2 by a λ arrow, so we accept.

Note that the NFA transitions on our reduced machine do not immediately show the λ clones in the verbose output, but they are behaving correctly.

Seems like everything is working well! Feel free to use this code on the grep part of HW4.

---

Footnote 1

Brian Kernighan made this video at around the time I had him as an academic adviser at Princeton, so that's how I remember him. His advice to me at the time was to take more theory courses (up to the point that we met I'd done mostly applications like music, graphics, and human computer interface). He was right! Theory is now also a huge passion of mine, as evidenced by these notes. I am eternally grateful for that push he gave me.

If there's one more thing I could go back and tell myself, it would be that it's OK if you struggle with the stuff at first, that's normal. Keep trying, and it will be amazing.