0
$\begingroup$

I have these two problems about regular expressions, can you help me?

1) Prove (ab)∗a = a(ba)∗.

I already proved this using induction and the definition of the kleene star * but I want to prove it now using NFAs, I drawed the NFAs for each but they don't seem to be equal from the picture and I'm stuck there.

2) Prove 0∗(11)∗((00)∗0∗(11)∗)∗0 = (0+11+00)∗0

For this I was think of creating a NFA for each side then converting them to a DFA and prove them equal using the product automata but since each side is very big that sounds like too much word to do by hand and I was wondering if there is a faster way.

Thanks in advance

Improve this question
$\endgroup$
2
  • $\begingroup$ Welcome to CS.SE! We generally prefer that you ask only one question per question. However, in this case, both of them appear to be covered by a previous question we have about proving equivalence of two regexps, so I'll mark this as a dup. If that one doesn't answer your question, edit this question or post a new one. FYI, we prefer that you search this site to look for related material before asking. Also, it's usually better to ask a conceptual question (one that will be useful even to someone else who isn't looking at exactly the same exercise you're working on now). $\endgroup$
    – D.W. ♦
    Commented Dec 17, 2015 at 18:26
  • $\begingroup$ See also cs.stackexchange.com/q/12624/755 and cs.stackexchange.com/q/50505/755 $\endgroup$
    – D.W. ♦
    Commented Dec 18, 2015 at 4:04

0

Reset to default

Browse other questions tagged or ask your own question.