Theory of computation help

[ray12]

prove the formula:

 

(111*)* = (11 + 111)*

 

thank you for helping

[vordhosbn]

[math](111^1)^1 \neq (11 + 111)^1[/math]

[ray12]

this is kleene star it can not be replaced by power 1, the formula (111*)* = (11 + 111)* is correct but i need to prove it..

[Aeternus]

I assume your alphabet is [math]\{1\}[/math]?

 

In this case, you can just proceed by induction on the length [math]n[/math] of the string. Take a couple of base cases to make it simple. It makes things much simpler if you first of all reduce it to (111*)* = 111*, since clearly 111* has any string of length 2 or greater, which is the same as (111*)*.

 

In the case [math]n = 0[/math], then due to the outer most Kleene Star in both cases, the empty word is in both languages.

 

In case [math]n = 1[/math], then as we have no string in either expression of length less than 2, no amount or concatenation or choice will result in a string of length one, so "1" is not in either language.

 

In case [math]n = 2[/math], then this is clearly in both languages from the definitions of Kleene star and +.

 

In case [math]n = 3[/math], then this is clearly in both languages from the definitions of Kleene star and +.

 

Assume for the induction hypothesis that we have the string [math]S[/math] of size [math]n[/math] in the language of both, and the string S' of size [math]n+1[/math] also in the language, and [math]n \ge 3[/math], then consider what happens if we have the string S'' of length [math]n+2[/math].

 

Clearly S'' is in the language 111* (as this matches any string of length 2 or greater). In case [math]n+2[/math] is odd, then we have that S of length [math]n[/math] is in the language (11 + 111)* and by the definition of the Kleene star S11 is also in the language, and the same argument holds if [math]n+2[/math] is even.

 

Basically, from 11 and 111, you can make any odd or even sized string of 1s of length greater than 2 by simply adding 11 to either repeatedly (to make all the even or odd sizes.