I have tried a few solutions to the above problem but havig huge doubts. Can someone please break it down for me step by step on how to reach a solution if I want to define a CFG with atmost 3 a's (over alphabets a,b)?
I thought of:
- S -> BABABAB
- A -> a
- A -> b
A -> e (blank)
B -> bB
- B -> b
- B -> e (blank)
( I have a feeling it is not right)
This is correct, but can be simplified. As this language is regular you can write it as the regular expressions $$b^*(a|\epsilon)b^*(a|\epsilon)b^*(a|\epsilon)b^*$$
Now we can turn this regular language into a CFG part by part. The overall structure is $$ S \rightarrow BABABAB$$ Now $b^*$ is expressed by $$ B \rightarrow bB\ |\ \epsilon$$ Notice that you don't need the rule $B \rightarrow b$ as we can reduce $B \rightarrow bB \rightarrow b\epsilon = b$.
$(a|e)$ is simply expressed by $$ A \rightarrow a \ |\ \epsilon $$
However your grammar is still correct, as $b^*(b|\epsilon) \equiv b^*$, so adding $A \rightarrow b$, gives you the same language.