CODEWITHSUNDEEP
regexregular-languageproof
Takobell
Takobell

Reputation: 23

Regular expression Proof

Can I get a hint on how to prove that for any regular expressions A and B

A(BA)* = (AB)*A

I tried to do it with induction but I get stuck after the base case,

Upvotes: 0

Views: 262

Answers (1)

Amadan
Amadan

Reputation: 198324

It works well with induction.

Base case is * being zero repetitions:

A (BA)^0 = A = (AB)^0 A

For one repetition, notice you can break AB down into A, then zero repetitions of BA, then B:

A (BA)^1 = A B (AB)^0 A = ABA = AB A = (AB)^1 A

This can be generalised: you can always strip off the first A and last B out of any (AB)^n and find (BA)^(n-1) inside: AB AB AB is the same as A BA BA B.

A (BA)^n = A B (AB)^(n-1) A = (AB)^1 (AB)^(n-1) A = (AB)^n A

Upvotes: 3

Related Questions