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
