# Chomsky Classification of Languages

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?

## 1 Answer

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.

• Thank you. I know that A is not regular and can prove this with the Pumping Lemma. A also is at least Type-1. How can I be certain that there doesn't exist a Type-2 grammar to describe it? – user1221 Jan 22 at 6:10