1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Please ask only one question per post, not two. If you have multiple questions, I recommend you post them separately. $\endgroup$ – D.W. May 6 at 5:50
  • 1
    $\begingroup$ $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$. $\endgroup$ – rici May 6 at 6:52
  • $\begingroup$ A language is not a grammar. No language is a regular grammar, for example. $\endgroup$ – Yuval Filmus May 6 at 6:57
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Goya May 6 at 14:57
  • 1
    $\begingroup$ Spend a few hours on the matter. I believe part of the issue is that you don't quite understand the definition of the language. Review set theory first. $\endgroup$ – Yuval Filmus May 6 at 14:59

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.