3 ms·
> You may recall that constructing an intersection automaton involves a cross product of NFAs I'm not sure what you mean by "cross product" here, but there's n
by thaumasiotes 4y ago
> You may recall that constructing an intersection automaton involves a cross product of NFAs
I'm not sure what you mean by "cross product" here, but there's nothing multiplicative involved. You just run both NFAs simultaneously. This gives you a number of states to track equal to the sum, not the product, of the two NFAs being intersected.
- cvoss 4y agoThat's one way to perform the computation, but that's not an NFA. The product construction involves making a single new NFA to do the job.
- thaumasiotes 4y agoIt is an NFA in every way except that you no longer have a single list of accepting states. "Doing two different things simultaneously" is the whole concept of nondeterminism. If you loosen the definition of "NFA" that you're working with from requiring a set of final states to requiring a function from a set of states to {0, 1}, everything will still work exactly the same way, all of your theorems will still hold, but intersecting two NFAs will consist of adding one state and adjusting the accept function.
- deleted 4y ago[deleted]
- codeflo 4y ago> It is an NFA in every way except So not an NFA. That's fine, you can always define "extended NFAs", and some variants are practically useful. For example, most practical "regex" implementations have features like backreferences that are very convenient, but strictly more powerful than DFAs. You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.
- thaumasiotes 4y ago> You just have to be aware that you lose all the well-established theory around NFAs if you do something like that. As I explicitly observed above: >> everything will still work exactly the same way, all of your theorems will still hold you don't lose any of the established theory by doing this.
- opportune 4y agoMost likely they mean Cartesian product instead of cross product. Also whatever you are describing is not an intersection per se as it’s not a permutation of the two possible combined states, it’s a construction for doing certain computations on intersected NFAs given its constituents. If each of two intersected NFA has three states the intersection can be up to 9 (the cardinality of the Cartesian product) states
- suyjuris 4y agoYou are thinking of the union, where you can indeed just put the two NFAs “side-by-side”. This does not work for the intersection though, there you need the product construction.