Context-free grammar for set {a,b} with specifications length/amt?

0
votes

This is for a practice exam question, so please explain answers and also give tips for thinking about similar problems. So I have the question:

Create a context free grammar for a language that accepts strings on the alphabet {a,b} where the number of a's are divisible by 3 or the length of x is divisible by 3, or both....where x = input string.

I'm struggling a lot with how I'm supposed to begin the problem.

I understand that a grammar for accepting strings from alphabet {a,b} that's divisible by 3 might look like:

0 -> a1 | b1
1 -> a2 | b2 
2 -> a | b | a0 | b0

Below is where I'm at so far, trying to keep track of both the total length of x and the amount of a's in x, for any combo of a's and b's:

0 -> a1 | b1
1 -> a2 | b3
2 -> a | a0 | b1
3 -> a | b | a2 | b4
4 -> a1 | b5
5 -> b | b1 | a2

The above is obviously wrong but I need some help. So example strings that should pass:

ababab
abaa
abbabb
1
context-free-grammar
You could try drawing a state machine, containing states for the number of as and bs required to accept the string. Then convert it into a grammar. – Loebl
Yea I've been trying to draw out an NFA but it seems a bit complicated also...I think I'm just thinking about this problem a bit wrong or something. – sGlow
Off the top of my head, if you only count as you would have 4 states: start, and count of as mod 3. Accepting state would be mod 3 = 0. Repeat that for bs and combine both state machines (cross product). (There are more approaches possible) – Loebl
My suggestion would be: don't "keep track of both". Define a CFG for "number of a's are divisible by 3" and one for "length is divisible by 3" and then just union them. It'll be ambiguous, but the question didn't disallow that. – Michael Dyck

1 Answers

0
votes

From my experience and schooling it is best to:

Build the grammar recursively

When building grammar of this type (certain number of terminals) it is best to do it recursively. Firstly you assume that your starting symbol is your desired string. You then split it into substrings, each still conforming to your rules until only terminals remain.

You approached the problem additively, by building the string from the ground up and trying to count how much terminals you have, which context-free grammars sadly cannot do (they can, but only for finite strings).

So the first rule would be

S -> 3

where

S...starting symbol
3..."multiple of three"

"Multiple of three" can either be string with 3 a's or string with length of 3.

3 -> A | L

where

A...string with 3 a's 
L...string with length of 3

To be able to build string of any length, we can add together any strings conforming to the same "rule of three".

A -> AA
L -> LL

Now - strings of length 3 are easy. 

L -> aM | bM
M -> aN | bN 
N -> a | b

3a string is just string of three a's with any number of b's dispersed between and around the three a's.

A -> bA | aB  
B -> bB | aC
C -> bC | a | aD
D -> bD | b

The 3a string is being built from left to right. Each rule can produce any number of b's until it caps them with an a. The final rule is able to produce any number b's on the right side.

Everything together :

S -> 3

3 -> A | L 
L -> LL | aM | bM
M -> aN | bN 
N -> a | b
A -> AA | bA | aB  
B -> bB | aC
C -> bC | a | aD
D -> bD | b

Remarks

  1. Build the grammar recursively
  2. Build the grammar from small units