[Solved]: A regular expression for a given formal language

Problem Detail: 

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?

Asked By : forrestGump

Answered By : jmad

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)^*$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2649

 Ask a Question

 Download Related Notes/Documents