# Defining Grammar for Given Language

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?

• Please ask only one question per post, not two. If you have multiple questions, I recommend you post them separately.
– D.W.
May 6 '20 at 5:50
• $A\to aA\mid a$ matches $\{a^n\mid n > 0\}$. $\{a^n\mid n \mod 3 \ne 1\}$ is $A\to aaaA\mid\epsilon\mid aa$.
– rici
May 6 '20 at 6:52
• A language is not a grammar. No language is a regular grammar, for example. May 6 '20 at 6:57

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$$
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.
• For the first context-free grammar that you list, could you explain why the production $S \rightarrow aS$ is needed? I understand the second two productions, but I'm having trouble seeing where $aS$ would ever be used.