Search code examples
regexautomaton

Regex for a word of a concatenation of 'a's and 'b's. a appears exactly n*2 times in a word and 'b' exactly n*3 times

I need to create a NFA (or DFA, don't know which it is going to be yet) for this language:

L(A) = { w ∈ {a,b}* | count(w, a) = 2i, count(w, b) = 3j, i, j ∈ ℕ }

count(w, z) defines how often a letter z appears in the word w. In this case it's a multiple of 2 for 'a', and a multiple of 3 for 'b'.

Examples of a valid word: babab, aabbb, bbaab, bbbabbba

I struggled creating an automaton for that, so I thought I'd try creating a regular expression for it first to turn it to a NFA using this method, because I can easily test it on a regex test sites. But that too didn't work. I ended up with too many combinations that seemingly had no end.

I don't know how to create a regular expression for that without using some sort of counting mechanism. Can somebody give me a hint?

Solution

  • You can model your automaton as six different states, each one describing the state of (count(w, a) mod 2, count(w, b) mod 3). There are six different possible states:

    (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2)

    Every time you read an "a", you go from the current state (e.g. (0, 1)) to the next a-corresponding state (-> (1, 1)). If you read another "a", you go back to the same state again (-> (0, 1)). The same with "b"s, but changing the b-value (e.g. (0, 1) -> (0, 2) -> (0, 0) -> (0, 1)).

    The only permited accept state is (0, 0).

    Using visual notation:

    http://cdn.imghack.se/images/ccea2c62451d81e477f73ac6fabc5134.png