How do you create a grammar?

Question

What are the paths to create a grammar of a specified type? For example, how do I define a type 3 grammar for the language of the strings on the alphabet {a,b} that contain an odd number of "a".

Answer 1

Wikipedia has a nice article on Formal grammar.

And here is a type $3$ grammar to deal with your example:

$S \to a$

$S \to bS$

$S \to Sb$

$S \to aSa$

$S \to Saa$

$S \to aaS$

An easy proof by induction on the number of applied rules shows that only strings with an odd number of $a$'s can be constructed. On the other hand, every such string is obtainable: Let $x$ be a counterexample of minimal length. By the rule $S \mapsto bS$, the leftmost character of $x$ must be $a$. By $S \mapsto Sb$ the last character of $x$ must be $a$. Write $x = aya$. Then $y$ has an odd number of $a$'s and, by the minimality of $x$, can hence be constructed. But then $S \mapsto aSa$ witnessed that $x$ can be constructed as well. Contradiction!

---

Note that this proof also shows that the rules $S \mapsto Saa$ and $S \mapsto aaS$ are not actually required. Something that I didn't notice until I went through the motions.

Answer 2

As a different approach from Stefan's, you could also (1) notice that your language is regular, (2) draw a DFA for it:

and (3) write out the corresponding regular grammar. This produces:

$$ \begin{align} S & \to bS \mid aT \\ T & \to bT \mid aS \mid {\varepsilon}\end{align} $$