Associated Topics || Dr. Math Home || Search Dr. Math

### 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

There seem to be so many combinations of possible solutions.

```

```
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
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search