Given the grammar $G=(\{S,A,B\},\{0,1,2\},P,S)$ where $$P\colon S\to0S\mid10A\mid2B,\;A\to2A+2,\;B\to00B+\lambda,$$ indicate the type of grammar using Chomsky's hierarchy, and find the language that it generates. $\lambda$ is the null word.
What I have done:
Since any rule has the form $tV$ (or $Vt$), $t$ or $\lambda$ then the type of $G$ is $3$ (it is a regular grammar).
To find the language, note that $S\to0S$ indicates that the words can start with $0$s, so at the moment we have: $$L(G)=\{0^n\ldots\ldots\ldots\ldots\ldots\mid n\geq0\}.$$ Also the words can start with $10$, so $L(G)=\{0^n10\ldots\ldots\ldots\mid n\geq0\}$, and the rule $A\to2A$ indicates that it has to continue with $2$s. At least there must be one $2$ because of $A\to2$, so at the moment we have: $$L(G)=\{0^n102^m\ldots\ldots\mid n\geq0,m\geq1\}.$$ The rule $S\to2B$ indicates that the word can start with $2$, and by the rule $B\to00B$ it follows that it has an even number of $0$, or nothing, because of $B\to\lambda$. Hence our final language is: $$\boxed{L(G)=\{0^n102^m2(00)^{2p}\mid n\geq0,m\geq1,p\geq0\}}.$$ However, I am missing the part of that a word can start with a lot of $0$s, or can start with $10$, or can start with $2$.
How can we deal with this problem?
Thanks!!
Starting from $S$, we have the possibility of producing $0$'s as many times as we want, until we choose one of the other two options, at which point we can no longer produce $0$'s. Let $X$ stand for the language generated by the option $10A$, and $Y$ stand for the language generated by the option $2B$. Then we have $$L(G) = 0^*(X + Y),$$ so now we just have to find out what $X$ and $Y$ are. $X$ begins with $10$ followed by one or more $2$'s, so $X = 1022^*$. Likewise, $Y$ begins with $2$ followed by zero or more $00$'s, so $Y = 2(00)^*$. Taken together, this gives $$L(G) = 0^*(1022^* + 2(00)^*),$$ or using set theory notation, $$L(G) = \{0\}^* \circ ((\{102\} \circ \{2\}^*) \cup (\{2\} \circ \{00\}^*)).$$ This also shows that although the language is originally described by a context-free grammar, it is in fact a regular language, answering the first part of the question.