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?
$\begingroup$
$\endgroup$
4
-
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$– RaphaelCommented 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$– wvxvwCommented Oct 7, 2015 at 9:18
-
$\begingroup$ can't you just use the AND operator? $\endgroup$– JMPCommented 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$– David RicherbyCommented Oct 22, 2015 at 7:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ For people reading who do not know what an NFA is, it is a Nondeterministic finite automaton. Additionally, a GNFA is Generalized Nondeterministic Finite Automaton $\endgroup$ Commented Jun 5, 2023 at 0:33