Given is a language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ ; where $N^{+}$ are the natural numbers excluding 0.
I have found a type-1 grammar to describe it:
$S \to A_1A_2$
$A_1 \to aA_1cc \;| \; abcc$
$A2 \to bA_2 \; |\; \epsilon$
However, this doesn't tell me much about the language's Chomsky type. How can I know if there exists a more restricted grammar and how can I find it?
The language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ is not obviously regular since finite automata do not have memory and hence it is not possible for them to determine the relation between $a$ and $c$.
Let us try to construct a Type-2 grammar for this language. Note that Type-2 grammars are of the form $V\to(V \cup T)^{*}$ where $V$ represents non-terminals and $T$ represents terminals. So our example would lead to something like this:
$S \to a\:A_1\:cc\:A_2 $
$A_1 \to a\:A_1\:cc\;|\;b$
$A_2 \to b\:A_2\;|\;\epsilon$
Hence we see that this is a Type-2 grammar according to the Chomsky hierarchy.
