Type 1 grammar for all even powers of terminal character 'a'. I'm new to formal languages. I'm stuck with the following question, and can't seem to find a solution to it.
I need a type 1 grammar for:
$$\{a^i \mid i=2j \text{ for some } j\ge0\}$$
I'm aware that type 1 grammar is a context-sensitive grammar where all productions are of type
$$aCb\to acb\;.$$
I can't find how to get a grammar for even powers of $a$.
Any help is appreciated. Thanks
 A: The natural idea is to use a production of the form $A\to aAa$ that generates a pair of $a$’s at a time; that clearly has the right form. We also need to be able to stop generating; $A\to aa$ does the trick, but you may need to convince yourself that it has the right form.
In a Type $1$ grammar with $\Sigma$ as its set of terminal symbols and $N$ as its set of non-terminal symbols the productions (with one exception) must be of the form $\alpha X\beta\to\alpha\gamma\beta$, where $\alpha,\beta\in(\Sigma\cup N)^*$, $X\in N$, and $\gamma\in(\Sigma\cup N)^+$. $A\to aa$ is of that form, with $\alpha$ and $\beta$ empty strings, $X=A$, and $\gamma=aa$. Thus, the grammar with productions
$$\begin{align*}
&A\to aAa\\
&A\to aa
\end{align*}$$
and initial symbol $A$ almost works: almost, because it doesn’t generate the empty word, which is in the language. This is where the exception that I mentioned comes in. The exception is that in order to be able to generate the empty word, we also allow $S\to\lambda$, where $S$ is the initial symbol, provided that there is no production with $S$ on the righthand side. A grammar that meets these conditions is:
$$\begin{align*}
&S\to\lambda\\
&S\to A\\
&A\to aAa\\
&A\to aa
\end{align*}$$
(You can replace $A\to aAa$ with $A\to aaA$ or $A\to Aaa$, if you prefer.)
A: Your language is $(a^2)^*$. Therefore it is a regular language and as such it can be generated by a Type 3 grammar, which mimics the behavior of the minimal automaton of the language. In your case
\begin{align}
  S &\to aT \\
  T &\to aS \\
  S &\to 1
\end{align}
