Defining Grammar for Given Language

Question

I'm attempting to practice for an exam and I'm having some trouble on one of the practice problems. The problem asks to identify a variety of language as regular grammar, context-free grammar, context-sensitve grammar, or unrestricted grammar. It also asks that if the grammar is regular or context-free, to write out the exact grammar. I'm not having trouble with two out of the 4 pieces of language. For instance, the easiest one is as follows:

$\{a^n$ where $n\ge0$, $n\pmod 3 \not= 1\}$ can be described by the regular grammar $A \rightarrow aA \mid a$

However, the language I am struggling with is:

$$\{a^n b^m \text{ where } n>1, m\ge1, n>m\}$$

and

$$\{a^{2n} b^{3n}\text{ where }n\ge1\}$$

I believe that the first language is context-free because I know that the language $a^nb^n$ is context-free from prior examples and can be described by the grammar $A \rightarrow aAb \mid ab$, however, in this version, $b$ is taken to the $m$ power rather than the $n$ and the bounds for $m$ and $n$ are different, and I'm not sure how that affects the grammar that describes it. Frankly, I'm not sure where to start with the latter piece of language... I don't know how to determine what type of grammar describes it, let alone the grammar itself if it is context-free or regular.

Could anyone help, or at least point me in the right direction?

Answer 1

Both of your languages are context-free and not regular. The first one can be generated using the following grammar: $$ S \to a S \mid a S b \mid aab $$ The second one can be generated using the following grammar: $$ S \to aaSbbb \mid aabbb $$

You can show that these languages are not regular using the pumping lemma or using Myhill–Nerode theory. Let me briefly indicate how to do so using the pumping lemma.

For the first language, suppose it were regular. Let $p$ be the constant promised by the pumping lemma. Then the word $a^{p+1} b^p$ is in your language. According to the lemma, it can be written as $xyz$, where $|xy| \leq p$ consists solely of $a$'s, and $y \neq \epsilon$. But then $xy^0z$ is not in your language.

The second language is even simpler, and left to you.