snippetMinor
How to get the intersection of two regular languages?
Viewed 0 times
thehowlanguagesregulartwogetintersection
Problem
I was trying to figure out the value of the following expression.
I tried drawing DFAs for
Is it the approach I should use? or is there any better way?
(0 | 1)00 ∩ (0 | 1)01I tried drawing DFAs for
(0 | 1)00 and (0 | 1)01 separately and combine them using a table. Is it the approach I should use? or is there any better way?
Solution
One approach is to convert each regexp to a NFA, then use the product construction to compute the intersection of those two NFA, then convert back to a regexp if necessary. Whether this is better or not, I can't say, as that depends what you mean by "better". One advantage of this approach is that it uses only standard techniques that hopefully you've already learned in your automata theory course and doesn't require memorization of specialized algorithms.
Context
StackExchange Computer Science Q#44120, answer score: 5
Revisions (0)
No revisions yet.