1
$\begingroup$

I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and in which between each pair of consecutive $a$'s there is an even number of $b$'s (and an arbirtary number of $x$'s).

For example, $babbxbbxabbxaabxxbax \in L$, $bab \in L$, while $abba \notin L$ and $abbbaa \notin L$.

What is the approach?

$\endgroup$
1
2
$\begingroup$

Try and build it step by step:

  • a language with an odd number of $a$'s: $a(aa)^*$;
  • between which there is an even number of $b$'s: $b^*a((bb)^*a(bb)^*a)^*b^*$;
  • and an arbitrary number of $x$'s: $(b+x)^*a(x^*(bx^*bx^*)^*ax^*(bx^*bx^*)^*a)^*(b+x)^*$.
$\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.