3

enter image description here! Problem This is my lecture notes;"Prove a*(b+ab*)=b+aab"
I am having trouble understanding what happened at line 3-> line 4;
What I understand Two things happen at those two line;

  1. Take ab* out of term ab* and term aa*b, results(Λ+aa*);
  2. Last term aa*ab* simplifies to aa*b* Because a in the middle is redundant;

Question is what happen to the * at aa*b(*)?

wtsang02
  • 18,603
  • 10
  • 49
  • 67
  • 1
    What is the carrot? Is that the standard regex carrot? If so, how is /a*/ == /^ +aa*/ == /^\s+aa*/? I'm confused >. – kikuchiyo Feb 22 '13 at 22:08
  • 1
    @close vote. Might as well close all reg expression questions like [these1](http://stackoverflow.com/questions/4952629/simplify-this-regular-expression) [these2](http://stackoverflow.com/questions/8859096/simplify-regular-expression-in-mathematica) – wtsang02 Feb 22 '13 at 22:10
  • There's probably a better site for CS questions like this. – Barmar Feb 22 '13 at 22:12
  • @kikuchiyo I think its Λ, which a* can be Λ or aa* because aa* must have at least 1 a. – wtsang02 Feb 22 '13 at 22:13
  • 1
    @Barmar Then I suggest closing all the tags that aren't directly related to programming. Since there's no code in these theory. – wtsang02 Feb 22 '13 at 22:16
  • @wtsang02: `aa*b*` actually got grouped into `(/\+aa*)ab*` and the 3rd term becomes the last term. I close this as too localized. – nhahtdh Feb 22 '13 at 22:33
  • @kikuchiyo: Λ denotes [the empty string](http://en.wikipedia.org/wiki/Empty_string). (In my experience it's usually denoted ε, but Wikipedia says that both λ and Λ are used as well.) – ruakh Feb 22 '13 at 22:39
  • Is that a photo of a photo on a screen? – Bergi Feb 22 '13 at 23:03
  • Photo on a screen. Its distance learning. – wtsang02 Feb 22 '13 at 23:06

1 Answers1

4

It looks like your professor left out lines 3⅓ and 3⅔:

Line 3:     b + ab* + aa*b + aa*ab*
Line 3⅓:    b + ab* + aa*ab* + aa*b      ←  commute last two terms
Line 3⅔:    b + Λab* + aa*ab* + aa*b     ←  ab* = Λab*
Line 4:     b + (Λ + aa*)ab* + aa*b      ←  distributive property
ruakh
  • 175,680
  • 26
  • 273
  • 307
  • 1
    +1 Even without CS knowledge you can just substitute `Λ` with `1` and apply basic algebra here. ;) – speakr Feb 22 '13 at 22:34