CODEWITHSUNDEEP
regexautomatadfa
Gipjoe
Gipjoe

Reputation: 73

Confusion about the Kleene star

I have been struggling to understand one key property about the closure of two union'ed expressions. Basically what I need to know exactly how the Kleene star works.

I.E If Regular Expression R = (0+1)* Does the expression have to evaluate to something like 000111/01/00001111, or can we have a unequal amount of 0's & 1's, such as 0011111/000001/111111/0000?

Upvotes: 4

Views: 1914

Answers (1)

jwodder
jwodder

Reputation: 57470

The amount of 0's and 1's can be unequal; you can even have the 0's and 1's in any order! a* means "zero or more as, where each a is evaluated independently"; thus, in a string matching (0+1)*, each character can match (0+1) without regard for how the other characters in the string are matching it.

Consider the pattern (0+1)(0+1); it matches the strings 00, 01, 10, and 11. As you can see, the 0's and 1's don't have to occur in equal amounts and don't have to occur in any specific order. The Kleene star extends this to strings of any length; after all, (0+1)* just means <empty>+(0+1)+(0+1)(0+1)+(0+1)(0+1)(0+1)+ ....

Upvotes: 6

Related Questions