patternMinor
Prove or disprove that two regular languages are equivalent
Viewed 0 times
equivalentlanguagesareregularprovetwothatdisprove
Problem
I have $L_1=\{b^+b^a(b+ab^a)^ab^\}$ and $L_2=\{(b^ab^a)^b^*\}$. I want to prove or disprove that they are equivalent.
I have proved that $L_2\subseteq L_1$ and I tried to transform the second expression in $L_1$ in order to find an expression contained in $L_2$ (without any luck so far). I tried also to find a word in $L_1$ that doesn't belong to $L_2$, but didn't have any luck either (all where in it).
Could anyone help?
I have proved that $L_2\subseteq L_1$ and I tried to transform the second expression in $L_1$ in order to find an expression contained in $L_2$ (without any luck so far). I tried also to find a word in $L_1$ that doesn't belong to $L_2$, but didn't have any luck either (all where in it).
Could anyone help?
Solution
It's hard to give hints without solving the problem for you.
Some general hints:
-
When working with regular expressions, the $^+$ sign ("one or more") is a useful shorthand:
$X^+ = XX^ = X^X$
$X^* = \epsilon \cup X^+$
For instance, in this case, we can write:
$L_1 = L(b^+b^a(b+ab^a)^ab^) = L(b^) \cup L_3$
$L_2 = L((\epsilon+(b^ab^a)^+)b^) = L(b^+(b^ab^a)^+b^) = L(b^) \cup L_4$,
with
$L_3 = L(b^a(b+ab^a)^ab^)$ and $L_4 = L(b^ab^a)^+b^*)$,
and since all members of $L_3$ and $L_4$ contain an $a$, $L_1 = L_2$ only if $L_3 = L_4$.
-
Expand the expressions into disjunctive form, $X_1 + X_2 + \ldots$, such that the subexpressions are, either:
Your hope is to quickly find, either:
-
No finite set of rewrite rules suffices to rewrite all equivalent regular expressions into each other. So you may fail to find a successful rewriting even when the expressions describe the same language.
-
When rewriting or finding a proof by induction, consider using not only regular expressions, but also set-theoretic descriptions of languages ("the language such that ...") and properties defined in such terms.
For instance, above I used the property that languages $L_3$ and $L_4$ are such that all of their strings contain an $a$.
If all else fails: a completely rigorous method to prove or disprove equivalence of regular expressions is to convert them to NFAs, then to minimal DFAs: two regular expressions are equivalent if and only if the resulting minimal DFAs are isomorphic. However, both conversion steps may cause an exponential blowup in size.
Some general hints:
-
When working with regular expressions, the $^+$ sign ("one or more") is a useful shorthand:
$X^+ = XX^ = X^X$
$X^* = \epsilon \cup X^+$
For instance, in this case, we can write:
$L_1 = L(b^+b^a(b+ab^a)^ab^) = L(b^) \cup L_3$
$L_2 = L((\epsilon+(b^ab^a)^+)b^) = L(b^+(b^ab^a)^+b^) = L(b^) \cup L_4$,
with
$L_3 = L(b^a(b+ab^a)^ab^)$ and $L_4 = L(b^ab^a)^+b^*)$,
and since all members of $L_3$ and $L_4$ contain an $a$, $L_1 = L_2$ only if $L_3 = L_4$.
-
Expand the expressions into disjunctive form, $X_1 + X_2 + \ldots$, such that the subexpressions are, either:
- the shortest strings in the language, or
- expressions that only generate longer strings.
Your hope is to quickly find, either:
- a string that is in one and not the other, or
- some kind of recurrence relation proving that they are $=$ or $\subseteq$.
-
No finite set of rewrite rules suffices to rewrite all equivalent regular expressions into each other. So you may fail to find a successful rewriting even when the expressions describe the same language.
-
When rewriting or finding a proof by induction, consider using not only regular expressions, but also set-theoretic descriptions of languages ("the language such that ...") and properties defined in such terms.
For instance, above I used the property that languages $L_3$ and $L_4$ are such that all of their strings contain an $a$.
If all else fails: a completely rigorous method to prove or disprove equivalence of regular expressions is to convert them to NFAs, then to minimal DFAs: two regular expressions are equivalent if and only if the resulting minimal DFAs are isomorphic. However, both conversion steps may cause an exponential blowup in size.
Context
StackExchange Computer Science Q#160764, answer score: 5
Revisions (0)
No revisions yet.