How should one continue to prove (or find) if two regular expressions are the same or equivalent?

Question

For example, in a task assigned to me, we were asked to find out if two regular expressions are equal or not.

(a+b+c)* and ((ab)**c*)* 

My question is: how to do this? If I draw transition graphs for both, and then pass a few lines through it and show that both TGs can accept it, is this sufficient evidence? If not, how do I do this? Is there a mathematical / axiomatic approach to this?

Thanks in advance.

EDIT: There is one more thing that I would like to clarify that relates to this issue. Are the two FA photographs pictured below the same?

i.e. Are (1) and (2) in the above figure the same?

Answer 1

There is an algorithm for determining whether they are equal:

• Build NFA lambdas corresponding to each RE using Klein's theorem
• Build a DFA for everyone using a subset / powertrain design
• (optional) Minimize DFA using the standard DFA minimization algorithm.
• Build DFA for L (M1) \ L (M2) and L (M2) \ L (M1) using the Cartesian Machine Machine
• (Optional) Minimize these CPMs.
• Determine whether each of them accepts any strings by checking all strings over an alphabet E of no more than | Q | (works due to pumping lemma for regular languages)

No novelty or genius is required; you can write a program for this (although in practice, using a powertrain design can be cumbersome, and minimizing both stages can be expensive).

EDIT: Yes, these DFAs are the same. The first is just an abbreviation for the second.

Answer 2

Two regular expressions R and T are equivalent if the language defined by R (i.e. the set of lines generated by the regular expression R) is equal to the language given by T. To prove equivalence for regular expressions, we use isolation proofs from set theory. What is if S1 is the set of lines generated by the regular expression R and S2 is the set of lines generated by the regular expression T, we must prove that S1 ⊆ S2 and S2 ⊆ S1. Both directions are necessary to prove the equality of sets.

- From lecture notes of CSc 4340 GSU Fall 09 (Dr. Raj Sunderraman)

Answer 3

Assuming

• Spaces are inserted to illustrate.
• ( ( ab )* * c* )* actually ((ab)*c*)* *,
• Each pattern is wrapped ^ and $ .

These regular expressions are NOT the same.

abccabcc will not match (a+b+c)* , but will match ((ab)*c*)*

How did I find this?

When I carefully looked at these patterns, I found 2 things.

• The first takes more than 1 of a and b {1,} . Thus, there will always be a sequence a and b sequence side by side. like aaaabb, aabbbbb etc. But in the second template, a and be will be side by side with one instance. like ab, ababab, abababab etc.
• c appears only 1 time after sequence a and sequence b. But in the second pattern, c can appear as many times as it can.

Answer 4

They are different, which is easily determined by quantifiers. For the first expression to match anything, it must contain c . Obviously, the second can do without c . (There are many other differences, but this should get you started).

Answer 5

((ab) ^^ c ^) ^ = (a ^ b ^ c ^) ^ = (a + b + c) ^

Answer 6

Since this is homework, I will not give you a complete answer, but I will tell you about a key fact that you need to know: for this final state language, DFA, which recognizes it with a minimum number of states, is unique.

By the way, I don’t think that your professor would assign this homework without teaching you how to do it. Get off the Internet and read lectures and / or tutorials.