World's most popular travel blog for travel bloggers.

# [Answers] How do the non-∪ variants of NFAs work?

, ,
Problem Detail:

I've only recently learned anything substantial about finite automata, and I've just come across some things I hadn't seen before. Specifically, that classic NFAs are ∪-NFA, and there are also these things ⊕-NFA , ∩-NFA and ⋆-NFA (I love unicode). These can all be seen in http://fastar.org/publications/PresentationFEW2006Geldenhuys.pdf or http://www.cs.sun.ac.za/~lvzijl/publications/fsmnlp2009.pdf

How are these different from the NFAs I'm familiar with?

Alright, I think I've figured it out. It can be seen in working with the transition function Δ : Q × Σ → P(Q), where Q is the set of states and Σ is the alphabet.

First, lets define some unary functions (P is powerset, of course):

• ∪ : P(S) -> S, ∪(X) = X1 ∪ X2 ∪ ... Xk where k = |X| (classic NFA)
• ∩ : P(S) -> S, ∩(X) = X1 ∩ X2 ∩ ... Xk where k = |X|
• ⊕ : P(S) -> S, ⊕(X) = X1 ⊕ X2 ⊕ ... Xk where k = |X| (symmetric difference NFA)

So basically, take a set of sets, and either and, or, or xor them all together.

Now, we extend the domain of our transition function to Δ : Q × Σ* → P(Q), where Σ* is a string of Σ, via the following recursive definition:

• Δ(s, e) = s, where e is the empty string
• Δ(s, xa) = ⋆({ s' ∈ Δ(s, x) | Δ(s', a) })

Where ⋆ can be any one of the three unary operators we defined above (and as specified in the second link in the original question, can be any associative and commutative operator on sets, converted into a combining unary function like above). The ⋆-NFA is the generalized NFA, so ⋆ is basically a wild card.

This is most intuitively understood in how an NFA is converted to a DFA by the subset construct. With a ∪-NFA, when you're creating your DFA states, you are taking the union of each result of the transition function from all the previous NFA states. With the other operators, its the intersection or symmetric difference of those states, respectively. If you take another look at that first link that I put in the original question, with this information in mind, it makes a pretty good example that should be relatively easy to understand. It seems this was the original intent of the slides, but without accompanying lecture it was a bit difficult to follow. I guess that about covers it.