Languages, Grammars

Date: 04/20/2003 at 16:33:40
From: Joni
Subject: Languages, grammars

Let L be the set of words w over the alphabet {a,b} that have an odd 
number of a's and a multiple of three b's.  Find a regular grammar 
that generates L.

Every time I came up with a "general formula" for the word accepted by 
an automaton, I couldn't come up w/ an automaton that would accept 
every word.

The simplest word in the language would have to be abbb or bbba.  I 
would think that any word of the form
   (aa)* (bbb)* a (aa)* (bbb)* (bbb) (aa)* (bbb)*
where * is greater than or equal to 0, would have to be accepted.  I
couldn't build an automaton that would cover all of these
possibilities.  Please, help.

There seem to be so many combinations of possible solutions.

Please help.

Date: 04/22/2003 at 07:26:29
From: Doctor Jacques
Subject: Re: Languages, grammars

Hi Joni,

It is not clear from your question whether or not you require the b's 
to be consecutive (the question seems to say that it's not the case, 
but your examples only show consecutive b's). I'll assume that it is 
not the case, i.e. that a word like 'abaabb' is to be accepted.

Let us write A for the number of A's and B for the number of b's. We 
want:

  A = 1 (mod 2)
  B = 0 (mod 3)

If we consider all the possibilities for (A mod 2) and (B mod 3), we 
have 6 cases:

  A    B    case
 ---------------
  0    0     C0
  0    1     C1
  0    2     C2
  1    0     C3
  1    1     C4
  1    2     C5

We use the symbols Ci as nonterminals, and we let Ci represent a 
string with the corresponding number of a's and b's (for example, C1 
is a string with an even number of a's and B = 1 (mod 3))

Now, we can write:

  C0 := <empty> | aC3 | bC2
  C1 := aC4 | bC0

and so on..., and we want to accept C3.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 04/22/2003 at 14:06:13
From: Joni
Subject: Thank you (Languages, grammars)

Doctor Jacques,

Thank you so very much for your explanation of the automaton. It makes 
perfect sense. I didn't know you could keep track of how many of the 
elements in your language you had seen so far by the different states.  
It seems to be a very efficient way. Thanks again,
Joni