1
$\begingroup$

I need some help with the understanding of Pumping Lemma for CFL

L = {all words over $\{a,b,c\}$ s.t. $n_a=n_b+2n_c\}$ where $n_a$ stands for number of $a$,$n_b$ - number of $b$ and $n_c$ number of $c$.
show that $L$ is not $CFL$

My thoughts:
Assume $L$ is $CFL$
take $w = b^{m}c^{2m}a^{3m}$.
$vy$ is either $b^{i} c^{j}$ or $c^{i} c^{j}$ or $c^{i} a^{j}$ or $a^{i} a^{j}$
take $w_1=uvvxyyz$
$w_1$ doesn't in $L$ since it doesn't satisfie the rule $n_a=n_b+2n_c $ Thus $L$ is not $CFL$

Can you show me where I'm wrong?

$\endgroup$
0
$\begingroup$

I hope it can help you.

Pumping lemma for CFL :

for infinite context-free language L

there exists an integer $m$ such that:

for any string $w\in L$ ,$|w| \ge m$

we can write $w=uvxy$

  1. $|vxy|\le m$

  2. $|vy| \ge 1$

and it must be: $\,\,\,\,\,\,uv^ixy^iz\in L$ $\,\,\,\,\,\,\,\,\forall i \ge 0 $


The language $L$ is not context-free language

Use the Pumping Lemma for context-free languages .we proof by contradiction (assume L is CFL pick any string of L with length at least m) examine $\underline{all}$ the possible locations of string $vxy$ in string $w$ and show contradiction in each case .


A language is context-free if there is a CFG for it

A context-free grammar (CFG) consists of a set of productions that you use to replace a variable by a string of variables and terminals. The language of a grammar is the set of strings it generates. A language is context-free if there is a CFG for it

your language in question is context-free language.

for $L=\{w\in\{a,b,c\}^*: n_a=n_b+2n_c , n_a \ge 0,n_b \ge 0,n_c \ge 0\}$ we have this grammar :

$\,\,\,\,\,\,\,\,\,S\to aaSc|A$
$\,\,\,\,\,\,\,\,\,A\to aAb|\epsilon$

so exist a context-free grammar that generating this language.

$\,\,\,\,\,\,\,\,$=> L is context-free language.

$\endgroup$

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.