Regular Expression for even-odd language of string

Question

I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of $a$'s. I am also interested in constructing a DFA and NFA for the language.

I tried

Even number of $b$'s = $(a^{\ast}ba^{\ast}ba^{\ast})^{\ast}$

Edit: I got DFA and NFA for odd number of $a$'s and even numbers of $b$'s and still unable to make regular expression which will allow only even number of $b$'s and odd nubmer of $a$'s . I also tried this Regular Expression

$(a(bb)^{\ast}(aa)^{\ast})^{\ast} $

Note: From above RE only those strings are generated which start from a but i want that RE which generate string of even number of $b$'s and odd number of $a$'s regardles of starting from a or b

Answer 1

Constructing a DFA (and thus an NFA), is quite trivial, so let's focus on the regular expression. (well, you can always convert a DFA into a regular expression, but this will not be very insightful, is it?)

Let's start simple. How do we construct an expression that describes only even length strings (over $\{a,b\}$)? Or even more simple, how to construct an expression for a language of only even length strings over $\{a\}$?

If there's only $\{a\}$ in the alphabet, we either have none, or they come in groups of two, so a possible answer is $(aa)^*$. When we have both $a$ and $b$, things become a bit more difficult. For instance, $(ab)^*$ is incorrect, since it doesn't allow $aa$. On the other hand, any expression of the form $(a^*b^*)^*$ not going to work, since we can't control the number of each letter. However, as before, we know that the letters must come in groups of 2, thus we should expect the form to be something like $(xy)^*$ with $x,y$ describing only even length strings, but what should $x,y$ be in this case? Well, we can just write all possible options, getting:

$$ ( aa+ ab+ ba+ bb)^*$$ (can you make it shorter?)

Now let's ask how do we get odd-length strings. Again, if the alphabet has only $a$, this would be quite easy - we can construct an even string, and add another $a$, getting: $$ (aa)^*a$$

A similar approach works for the case where the alphabet is of size two: $$ ( aa+ ab+ ba+ bb)^*(a+b)$$

Now a sanity check: we add the "a" or "b" only at the end. Maybe it comes in the middle, and not in the end?! Convince yourself that adding at the end is equivalent, and gives the right answer.

Finally, try to use the above ideas to solve your question. There is still some leap left, so don't give up too fast. Some hints:

Hint1: the length of the final string must be odd (if it contains both letters)

.

Hint2: get rid of one letter, so the length is even, and furthermore, both letters appear an even number of times!

.

Hint3: don't forget to put back the one letter you got rid of. Convince yourself you placed it in the correct place...

Answer 2

Here is a pipeline of simple steps that leads you to the result:

1. Build an automaton $A_a$ for $L_a = \{ w \in \{a,b\}^* \mid |w|_a \in 2\mathbb{N}+1 \}$.
2. Build an automaton $A_b$ for $L_b = \{ w \in \{a,b\}^* \mid |w|_b \in 2\mathbb{N} \}$.
3. Construct the product automaton $A$ for $L_a \cap L_b$.
4. Convert $A$ into a regular expression.

The construction in 3. is a standard one I'd expect to be given in your lecture or textbook; usually, it's how we prove that the regular languages are closed against intersection.

Note how this approach generalizes to any regular language that can be characterized by elementary operations on other regular languages (which are simpled to express). Essentially, you work along the closure properties of the class of regular languages.

Answer 3

I will propose a way that requires almost no creativity but instead you will need a heavy algorithmic artillery.

You already found the RE $R_1=(a^*ba^*ba^*)^*$ such that $R_1$ denotes all the strings with a even number of b's(without restriction in the numbers of a's).

Now you can easily find the RE for the strings with a odd number of a's. $R_2=(b^*ab^*ab^*)^*b^*ab^*$. Lets name this language $L_2$.

We know that your language of interest $L=L_1\cap L_2$. I don't know if there is a way to directly intersect regular expressions. But I found a way to intersect DFA's. So the next step are:

1.- Transform the RE's into DFA's. You can do that directly following this algorithm: RE->DFA. One advantage of that algorithm is that you generate a minimum DFA so your drawing skills will not be challenged but you always can transform RE->NFA->DFA.

2.- Next you have to intersect the two DFA's using this algorithm: DFA intersection

3.- Finally you can transform your DFA into a RE following this algorithm: DFA->RE

I would do this only if it is my only option because creativity can save a lot of work.

Answer 4

The hard way to do it

You might be able to deduce this system by pure insight, especially after seeing the answer that this method comes up with. But as Einstein once said in a lecture: "What follows has been done much more elegantly by Minkowski, but chalk is cheaper than gray [brain] matter, so we will take it as it comes."

The dumbest machine which builds strings in this language looks like:

                           [even, odd]
             (append "b") /           \ (append "a")
                         /             \
{start}  --> [even, even]               [odd, odd]
                         \             /
             (append "a") \           / (append "b")
                           [odd, even]
                                |
                                |
                              {end}

where [] are states of the system, () are actions taken while following an edge (either way), and {} are special pointers to enter and terminate the process. From now on the actions will all be "append a string matching this regex", so I will just include the regex in those parentheses and be done with it.

Now we remove states. When we remove a state X, we take every inbound arrow to that state from every other state Y, and create an arrow in its place from Y to every Z, where Z ranges over all of the destinations of outbound arrows of X. There are two subtleties: first, when X has an arrow pointing to itself (none of these do yet, but they will), in which case our regexes all need to include a repetition operator *; they all take the form (Y-to-X)(X-to-X)*(X-to-Z). The other subtlety is that if an arrow of the same start and end already exists, we can (and should) concatenate their regular expressions with the alternation operator | that matches if either the regex on the right or left matches.

Now, it matters which states you remove, and in which order, for getting this regex to look simple. There are other forms which look less simple. We will remove the right node [odd, odd] first, then [even, even], in order to preserve an aesthetic symmetry that will keep our regex simple.

So let's remove [odd, odd]. This means that you need to add four arrows: one arrow each from [even, odd] and [odd, even] back to themselves, and then one arrow from [even, odd] to [odd, even], and one arrow back.

The arrow from [even, odd] to itself is labeled (aa) while the arrow from [odd, even] to itself is labeled (bb). The path from [even, odd] to [odd, even] is (ab) and the reverse is (ba).

Now we want to remove [even, even]. This is tricky because the {start} pointer is pointing at it, so we will instead point the {start} at some node [start] which is otherwise exactly like [even, even] but has no other inbound arrows. This removal symmetrizes the system nicely:

{start} ---> [  start  ]
            /           \
       (b) /             \ (a)
          V    (ab|ba)    V
    [even, odd]=======[odd, even] ---> {end}
       V   ^             V   ^
       |___|             |___|
      (aa|bb)           (aa|bb)

(Here the double line is again a symmetric transition.)

Eliminating [even, odd] is the tricky part; it induces a loop in [odd, even] which must now take the form of:

aa   |   bb   |   (ab | ba) (aa | bb)* (ab | ba)

where I've added spaces added for clarity, but it also has to add onto the [start] -> [odd, even] arrow:

a    |    b (aa | bb)* (ab | ba)

Thus we have simply

(a|b(aa|bb)*(ab|ba))(aa|bb|(ab|ba)(aa|bb)*(ab|ba))*

It has two parts: the first parses the minimal string that contains an odd number of a and an even number of b, by saying "either we start on an a and all is good or we start on a b and take further characters in pairs: if we see an aa or bb we keep going, if we see an ab or ba we have found the minimal string."

The second parses any string which has an even number of a and an even number of b, again by taking characters in pairs: if it sees an aa or a bb it continues, otherwise if it sees an ab or a ba it skips as many aa and bb tokens as it can until it finds a corresponding ab or ba (doesn't matter which).