HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to get the intersection of two regular languages?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thehowlanguagesregulartwogetintersection

Problem

I was trying to figure out the value of the following expression.

(0 | 1)00 ∩ (0 | 1)01

I 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.