Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Regular expression for strings with even number of a's and odd no of b's

Im having a problem in solving the problem:- Its an assignment, i solved it, but it seems to be too long and vague, Can anyboby help me please......

Regular expression for the strings with even number of a's and odd number of b's where the character set={a,b}.

like image 457
Abu Mathew Avatar asked Sep 13 '10 07:09

Abu Mathew


People also ask

What is the regular expression for the language of an odd number of B's?

Solution : The regular expression for odd number of a is b*ab*(ab*ab*)* and corresponding automata is given in Figure 6 and minimum number of states are 2.

What is a regular expression for a set of strings of 0s and 1s with even number of 0s?

The expression +0+1 describes the strings with length zero or one, and the expression (0 + 1)*(00 + 10 + 11) describes the strings with length two or more. ¯ (c). All strings containing an even number of 0's: 1*+ (1*01*0)*1*.

What is the regular expression of even even language?

Solution: Since any string of even length can be expressed as the concatenation of strings of length 2 and since the strings of length 2 are aa, ab, ba, bb, a regular expression corresponding to the language is ( aa + ab + ba + bb )*.

What does '$' mean in regex?

$ means "Match the end of the string" (the position after the last character in the string).


2 Answers

One way to do this is to pass it through two regular expressions making sure they both match (assuming you want to use regular expressions at all, see below for an alternative):

^b*(ab*ab*)*$
^a*ba*(ba*ba*)*$

Anything else (and, in fact, even that) is most likely just an attempt to be clever, one that's generally a massive failure.

The first regular expression ensures there are an even number of a with b anywhere in the mix (before, after and in between).

The second is similar but ensures that there's an odd number of b by virtue of the starting a*ba*.


A far better way to do it is to ignore regular expressions altogether and simply run through the string as follows:

def isValid(s):
    set evenA to true
    set oddB to false
    for c as each character in s:
        if c is 'a':
            set evenA to not evenA
        else if c is 'b':
            set oddB to  not oddB
        else:
            return false
    return evenA and oddB

Though regular expressions are a wonderful tool, they're not suited for everything and they become far less useful as their readability and maintainability degrades.


For what it's worth, a single-regex answer is:

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

but, if I caught anyone on my team actually using a monstrosity like that, they'd be sent back to do it again.

This comes from a paper by one Greg Bacon. See here for the actual inner workings.

like image 197
paxdiablo Avatar answered Oct 13 '22 08:10

paxdiablo


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

(Even-Even has even number of Aas and b's both)

Even a's and odd b's = Even-Even b Even-Even

This hsould work

like image 31
Veenu Avatar answered Oct 13 '22 08:10

Veenu