2
$\begingroup$

I'm having trouble finding the language represented by the following:

(AA|BB)*

Should the expression be read as... ( A (A|B) B ) * or... ( (AA) | (BB) )*

If that isn't clear, should this produce something like... ABABAB or should it produce AABBAABBBBAA

My guess is that AABBAA is part of the represented language, while AB is not.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You are correct. The notational convention is that concatenation binds tighter than alternation. $\endgroup$
    – reinierpost
    Jun 13, 2014 at 10:44

3 Answers 3

Reset to default
-1
$\begingroup$

This Regular expression $(AA|BB)*$ can accept any string having two consecutive A's or B's i.e. even number of consecutive A's and even number of consecutive B's. so AABBAA is in it but AB is not in it.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ No! AAA and ABBA have at least two consecutive A's or B's but neither matches the regular expression. $\endgroup$
    – David Richerby
    Feb 3, 2014 at 11:06
  • $\begingroup$ Hi David, I missed this point, I will make edit to my answer. $\endgroup$
    – codeomnitrix
    Feb 3, 2014 at 13:43
6
$\begingroup$

This depends entirely on convention; with respect to a (proper) formal definition, the expression is invalid as it not properly parenthesised. I'd say that typically, the order is (from stronger to weaker binding)

  • Kleene Star/Plus (also finite versions),
  • concatenation,
  • alternative.

Note that this corresponds (visually) to exponentiation over multiplication over addition in basic arithmetics, so it's probably the natural way.

That is,

  • $10^*1$ is read as $1(0)^*1$ and
  • $10|01|11$ as $(10)|(01)|(11)$.

Note that I still drop parentheses due to associativity of concatenation and alternative.

Improve this answer
$\endgroup$
0
$\begingroup$

I think it is :

  (AA+BB)* =AABBAABBBBAA

if it has to be like starting with A and ending with B concept then probably they would have provided the parenthesis like:

   (A(A+B)B)*  =ABABABABB
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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