3

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?

Community
  • 1
  • 1
user1202727
  • 63
  • 2

3 Answers3

5

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

Juan Lopes
  • 10,143
  • 2
  • 25
  • 44
  • I upvoted you, and then you added a great picture, and I wish I could upvote you again. :-) – ruakh Nov 17 '13 at 21:49
  • Is there a step by step approach to this kind of problem? It is hard coming up with a solution without using some kind of technique, if there is any. Your suggested mod2 and mod3 approach was understandable, but do you have to come up with that 'just like that' or are there well-known techniques for that? There seem to be techniques/approaches for everything (like minimizing a DFA or converting a NFA to a DFA). – user1202727 Nov 17 '13 at 22:26
  • What software did you use to generate that image? – Steve P. Nov 18 '13 at 00:11
  • @user1202727 Don't know if there is a general technique to solve this kind of problem. Most of the times in math, solving a problem is just a matter of detecting these patterns using intuition (maybe this is why most of IQ tests are questions of pattern recognition). – Juan Lopes Nov 18 '13 at 14:32
0

Lets see, you need a even number of a's, that gives you two states

a-even
a-odd

and you need a multiple of three for b's:

b-ok
b-one
b-two

Combining these states, we can build the following grammar:

S(*) -> a A | b B1
A -> a S | b B1A
B1 -> b B2 | a B1A
B1A -> a B1 | b B2A
B2 -> b S | a B2A
B2A -> a B2 | b A

So, this is a regular grammar, all rules have right recursion with one terminal simbol and at most one non-terminal, hope the grammar helps.

Augusto Hack
  • 2,032
  • 18
  • 35
0

The simplest approach to validating your input is to use a regex for your requirement:

^(?=((b*a){2})*b*$)(?=((a*b){3})*a*$)[ab]*$

This uses look aheads to assert the quantity of "a" is a multiple of 2 (including zero), and similarly for "b" bring s multiple if 3.

See a live demo of this regex working with your examples and some invalid examples.

Bohemian
  • 412,405
  • 93
  • 575
  • 722