0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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$ – user1221 Jan 22 at 6:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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