Languages, GrammarsDate: 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 |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/