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
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.)