Finding a Regular Expression for an Intersection of Two Regular Expressions

PAIR of regular expressions is ((ss*)t*) and ((ss*) + (tt*)).

How do I find a regular expression that represents the intersection of the languages defined by the pair?

  • 1
    $\begingroup$ What have you tried and where did you get stuck? Hint: go via automata; all constructions are in the book resp. given in lecture (probably). $\endgroup$
    – Raphael
    Commented Oct 7, 2015 at 7:03
  • $\begingroup$ Think about it like this: are there any words in first language which begin with $t$? - if not, you can throw away the $tt^*$ from the second expression. Now, you have two very similar expressions: $ss^*t^*$ and $ss^*$ - from here the answer should be obvious ;) PS. The parenthesis in your question are suspiciously extraneous. Are you sure you've copied the question correctly? $\endgroup$
    – wvxvw
    Commented Oct 7, 2015 at 9:18
  • $\begingroup$ can't you just use the AND operator? $\endgroup$
    – JMP
    Commented Oct 16, 2015 at 13:06
  • $\begingroup$ @JonMarkPerry In the context of theoretical computer science, regular expressions have only concatenation, OR and *. Adding AND wouldn't change the power of the system but, by convention, it's not there. $\endgroup$ Commented Oct 22, 2015 at 7:27

1 Answer 1


I believe, you can convert both expressions to NFAs, then construct a NFA that is the intersection of both NFAs. From this NFA, convert it into a GNFA and from the GNFA convert it on the regular expression, the result is the intersection of both expressions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.