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.

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

3 Answers 3

-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.

$\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$ Feb 3, 2014 at 11:06
  • $\begingroup$ Hi David, I missed this point, I will make edit to my answer. $\endgroup$ 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.

$\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
$\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.