Results 1 to 3 of 3

Math Help - Find a String of Minimum Length Not in the Language

  1. #1
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    68
    Thanks
    1

    Find a String of Minimum Length Not in the Language

    In each case below, find a string of minimum length in {a,b}* not in the language corresponding to the given regular expression.

    a. b*(ab)*a*

    b. (a* + b*)(a* + b*)(a* + b*)

    c. a*(baa*)*b*

    d. b*(a + ba)*b*
    ================================================== ================================================== ================

    I'm confused. Is the question asking me to give a string that shouldn't be in the expression? Well here are my attempts. Someone please let me know if I'm right or wrong:

    My Attempted Solutions

    a. ba. a,b,and null are in the expression for strings of length 1 or less. For strings of length 2 or less, we have bb, aa, and ab but NOT ba.

    If the answer above is correct why? The commutative law says ab=ba. So for part a shouldn't the (ab)* in the expression equal (ba)* ?

    b. ab. I don't know why. (Because the expression is in product of sums form?)

    c. ab. The middle string, (baa*)* lets you have any amount of that string. The inside of the parentheses could also be (ba)* because the a* term could be absent. So I could have any amount of ba's but not ab.

    d. aa. The expression says you can have any amount of b's and (a + ba) terms. So aa wouldn't be in the expression.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Find a String of Minimum Length Not in the Language

    These problems frequently use the Pumping Lemma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2013
    From
    USA
    Posts
    68
    Thanks
    1

    Re: Find a String of Minimum Length Not in the Language

    Quote Originally Posted by SlipEternal View Post
    These problems frequently use the Pumping Lemma
    I had to do some googling to figure out what you were talking about...

    I did find the following Stackoverflow Explanation to be of some help...Okay let me try to re-do these solutions:

    a. ba...that answer should be the same

    b. ab...that should be the same also. The expressions states you can have any amount of a's or any amount of b's but not both.

    c. ab..should also be the same. In a*(baa*)*b* I could choose not to have the first a and/or the last b making it (baa*)*. Get rid of a* and I have (ba)*. b has to be first so ab wouldn't be in the expression.

    d. Same concept as c, b*(a + ba)*b* --> (a + ba)* . Now here I can have any amount of a's or any amount of ba's but not both. However instead of aa being the answer I do believe I will go with ab instead. In (a + ba)* if I choose to have any number of ba's then a and b have to be in that specific order. So ab would be the answer.

    Are those answers better or am I still off?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: November 14th 2013, 08:39 AM
  2. Bit String Length
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 11:19 AM
  3. Length of string around circular rod
    Posted in the Geometry Forum
    Replies: 8
    Last Post: December 15th 2008, 10:13 AM
  4. Find the minimum length...
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 27th 2008, 11:18 AM
  5. Minimum Length
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 6th 2007, 07:48 PM

Search Tags


/mathhelpforum @mathhelpforum