1
$\begingroup$

If you have a Kleene star applying to a set of characters not in any closure, does it apply to that whole string, or just the one character it belongs to? Any examples I search don't specify.

For example:

(A)BB*

Does this mean 1: one A followed by zero to an infinite number of BB's, or does it mean 2: one A followed by at least one B and zero to infinite number of B's?

$\endgroup$
2
$\begingroup$

Kleene stars applies to the character(s) it belongs, so in your example the correct option is the 2° one.

ABB* = {AB, ABB, ABBB, ABBBB, ..}

A(BB)* = {A, ABB, ABBBB, ABBBBBB, ..}

$\endgroup$
  • $\begingroup$ Thank you, any explanations of the Kleene star always had it around brackets, which was clear but never when they were outside. $\endgroup$ – NateH06 Jan 22 '17 at 11:14
  • $\begingroup$ "Kleene stars applies to the character(s) it belongs" Just using the word "belong" instead of "apply" doesn't actually convey any information. Which characters does it "belong" to? $\endgroup$ – David Richerby Jan 22 '17 at 11:35
1
$\begingroup$

Conventionally, the Kleene star applies only to the character immediately before it, so $ABB^*$ is $AB$ followed by some number of $B$s. Parentheses are used to make it apply to a sequence of characters; e.g., $A(BB)^*$ is $A$ followed by some number of pairs of $B$s.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.