I have the following language: $L = \{a^{2m + k}b^{3n+\ell}c^{m+n} \mid \ell\leq3 \space\text{and}\space k\gt2\space\text{and}\space m,n \in\mathbb{N}\}$

  1. Is it regular?
  2. Is it context-free?

What I have so far -

1) This language looks similar to $\{a^{n}b^{m}c^{m+n}\}$ which I know is irregular, so I think L is also irregular. My proof: I assume L is regular, so (from the Pumping Lemma), there is number p. The word I chose is $w = a^{2p+3}b^{3p+3}c^{5p}$, $xy=a^{q}, q\le p, y=a^{r}, r \gt 0, x = a^{q-r}$. So now w is $w=a^{q-r}a^{r}a^{2p+3-q}b^{3p+3}c^{5p}$. Now when trying to pump $w=a^{2p+3+r(i-1)}b^{3p+3}c^{5p}$. So $5p=2p+rp+3p=5p+rp$, but $r\gt0$ so this is contradiction. Hence L is not regular.

2) Now I'm trying to build a grammar $G$ and show that $L =L(G)$

$G=\langle V,\Sigma, P, S \rangle$ where $P = \{S \to N|M, M \to aaMc|aaaM_1,M_1 \to aM_1|N,N \to bbbNc|N_1|\varepsilon, N_1 \to bbb|bb|b \}$

Is my proof of 1) right? Is my approach for 2) right? How can I continue and show that $L=L(G)$. I know that my grammar is a bit complex, so I'd like to hear easier approach to build one.


Your proof for 1) looks alright though it depends a bit on the form of the pumping lemma that you are using.

The grammar looks fine, too, just $aaM_1$ instead of $aaaM_1$ in the second rule. Proofs for which language a grammar generates are very ugly. In you case, the grammar is not so bad, because it is linear and thus you just have to track one line of nonterminals. Show that

  1. all derivations generate words from the language
  2. for every word of the language there exists a derivation.

Both probably by verbose argumentations.


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.