2,225 views

1 Answer

Best answer
5 votes
5 votes

Proving the identities of Regular expression is a very difficult task. Its belong to the PSPACE complexity. Here is the reference. Link1 and Link2

There is an algorithm to determine whether they are equal:

  1. Construct NFA-lambdas corresponding to each RE using Kleene's theorem.
  2. Construct DFAs for each using the subset/powerset construction
  3. (optional) Minimize the DFAs using a standard DFA minimization algorithm. 
  4. Construct DFAs for L(M1) \ L(M2) and L(M2) \ L(M1) using the Cartesian Product Machine construction
  5. (Optional) Minimize these CPMs.
  6. Determine whether each one accepts any strings by testing all strings over alphabet E of size no greater than |Q| (works due to the pumping lemma for regular languages)

For the Gate Points of View, if you want to prove that two regular expression same or not then prove it by contradiction. It means that generate a string from one of the grammar which can not be generated by the other grammar. A general advice is that you should always start from the most basic string.

This about the given regular expression. The most basic string which can be generated by the RHS regular expression is $\{ \epsilon, a, ab, ba \} $ 

Now check if this string can be generated from LHS regular expression or not? Yes they all can be generated. 

You can think like this. Now think some string which can be generated by the LHS regular expression and see that can be generated by RHS regular expression or not. That's it. 

selected by

Related questions

3 votes
3 votes
2 answers
1
Sunil8860 asked Sep 4, 2017
783 views
2 votes
2 votes
2 answers
2
Kapil asked Jul 8, 2016
1,337 views
The equality of two regular expression is computed in? Give reasons also..Constant Timepolynomial timelogarithmic Polynomial timeExponential time
1 votes
1 votes
2 answers
3
shekhar chauhan asked Jun 8, 2016
1,750 views
If r1 and r2 are 2 Regular Expression Such thatr1 = (a+b)* r2 = (a*+b*+a*b*+b*a*)What are the different case's in which r1 = r2 ?Please Explain with an example