CODEWITHSUNDEEP
regexformal-languages
user1193839
user1193839

Reputation: 37

Minimal Length of a regular Expression

Working on my homework for a class and I came to this question:

For each of the following regular expressions, give minimal length strings that are not in the language defined by the expression.

  1. (bb)*(aa)*b*
  2. a*(bab)*∪b∪ab

I'm going to try to only get help on the first one and see if i can figure out the second. Heres what I Know: Kleene * indicates 0 or more possible elements. and union of a set is the set containing all elements of set a and set b without repeating an element. Working through the first problem starting by inserting lambda, i get:

1st run: bbaab
2nd: bbbbaabaabbaabbbbaab
3rd: bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab

If I'm doing that correctly than strings of length 0 to 5 are not in the language. Am i doing this correctly?

Upvotes: 0

Views: 432

Answers (1)

Petar Ivanov
Petar Ivanov

Reputation: 93030

The first regular expression is matching any word that starts with an even number of 'b's (zero included) followed by an even number of 'a's (zero is ok), then followed by some 'b's.

This means that the empty string is in the language, as well as the string "b". However, the string "a" is not in the language.

Thus all the minimal length string that are not in the language is "a".

The second regex matches on "", "a" and "aa" (by a*(bab)*) and also on "b" and "ab". However it doesn't match on "ba" and "bb".

Thus the minimal strings are of length 2: "bb" and "ba".

Upvotes: 3

Related Questions