# Thread: Find a String of Minimum Length Not in the Language

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.

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

These problems frequently use the Pumping Lemma

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

Originally Posted by SlipEternal
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?