CODEWITHSUNDEEP
automataautomata-theory
Jaffar
Jaffar

Reputation: 75

Regular expression for odd length of a's and odd length of b's

I am stuck in this question and took me 1 hour but still failed to solve it.

The language can contain any combination of "a" and "b" but both a's and b's length must be odd (individual length not combined length of string)

I tried to identify different combinations first of all which are possible, I was only able to solve this case

The expression I made to solve this combination was:

a(aa+bb)*b + b(aa+bb)*a + a + b

However I tried to solve other combinations but was not able to solve them. Please I need some assistance.

Upvotes: 2

Views: 754

Answers (1)

Patrick87
Patrick87

Reputation: 28312

We have an answer here for even numbers of a's and b's:

Even-Even = (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

To get Odd-Odd we can construct a regular expression from this that must work:

Odd-Odd = ab(aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
        + ba(aa+bb+(ab+ba)(aa+bb)*(ab+ba))*
        + a(aa+bb+(ab+ba)(aa+bb)*(ab+ba))*b
        + b(aa+bb+(ab+ba)(aa+bb)*(ab+ba))*a
        + (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*ab
        + (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*ba

Perhaps there is a simpler regular expression that works, perhaps not. But, provided the solution for even-even is correct, this should be right

Upvotes: 0

Related Questions