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.

  • $\begingroup$ 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? $\endgroup$
    – iMazing
    Jan 22 '19 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.