Skip to main content
Computer Science

Return to Answer

I corrected some mistakes (mixing up x and y). Then I got a bit carried away trying to maximize the clarity of the proof.
Source Link
edit approved Jan 25, 2017 at 10:21
Theodore Norvell
edit approved Jan 25, 2017 at 10:21
Theodore Norvell
  • 540
  • 2
  • 8

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose L$L$ is context-free. ThenThe pumping lemma says there exists some integer $p \ge 1$ such that every string s$s$ in L$L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

From definitionLet $s$ be a string in $L$ longer than $p$, and $|s|=2^k$ for some$u$, $k\in\mathbb{N}$$v$, but $|uv^nw^nx|=|uwx|+n*|vx|$$w$, $x$, and $y$ have the properties given by the pumping lemma. SupposeThus $$|uwx|=2^a, |uvwxy|=2^b (b>a)$$ then$uwy, uvwxy, uv^2wx^2y\in L$. Let $$|uv^2wx^2y|=2|uvwxy|-|uwx| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$$a$ and $b$ be such that $$|uwy|=2^a, |uvwxy|=2^b$$ Note $b>a$. Then $$|uv^2wx^2y|=2|uvwxy|-|uwy| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ But $2^a(2^{b+1-a}-1)$ is not a power of 2, i.e.and so $uv^2wx^2y\notin L$.

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose L is context-free. Then there exists some integer $p \ge 1$ such that every string s in L where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

From definition, $|s|=2^k$ for some $k\in\mathbb{N}$, but $|uv^nw^nx|=|uwx|+n*|vx|$. Suppose $$|uwx|=2^a, |uvwxy|=2^b (b>a)$$ then $$|uv^2wx^2y|=2|uvwxy|-|uwx| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ is not a power of 2, i.e. $uv^2wx^2y\notin L$.

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose $L$ is context-free. The pumping lemma says there exists some integer $p \ge 1$ such that every string $s$ in $L$ where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

Let $s$ be a string in $L$ longer than $p$, and $u$, $v$, $w$, $x$, and $y$ have the properties given by the pumping lemma. Thus $uwy, uvwxy, uv^2wx^2y\in L$. Let $a$ and $b$ be such that $$|uwy|=2^a, |uvwxy|=2^b$$ Note $b>a$. Then $$|uv^2wx^2y|=2|uvwxy|-|uwy| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ But $2^a(2^{b+1-a}-1)$ is not a power of 2, and so $uv^2wx^2y\notin L$.

trivial grammar, formatting
Source Link
rphv
rphv
  • 1.6k
  • 12
  • 25

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context free.language-free language according to Pumping lemma for context-free languages.

Suppose L is context-free, then. Then there exists some integer $p \ge 1$, such that every string s in L thatwhere $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

From definition, $|s|=2^k$ for some $k\in\mathbb{N}$, but $|uv^nw^nx|=|uwx|+n*|vx|$. Suppose $$|uwx|=2^a, |uvwxy|=2^b (b>a)$$ then $$|uv^2wx^2y|=2|uvwxy|-|uwx| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ is not a power of 2, i. iee. $uv^2wx^2y\notin L$.

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context free.language according to Pumping lemma for context-free languages.

Suppose L is context-free, then there exists some integer $p \ge 1$, that every string s in L that $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$

From definition, $|s|=2^k$ for some $k\in\mathbb{N}$, but $|uv^nw^nx|=|uwx|+n*|vx|$. Suppose $$|uwx|=2^a, |uvwxy|=2^b (b>a)$$ then $$|uv^2wx^2y|=2|uvwxy|-|uwx| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ is not a power of 2. ie. $uv^2wx^2y\notin L$.

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context-free language according to Pumping lemma for context-free languages.

Suppose L is context-free. Then there exists some integer $p \ge 1$ such that every string s in L where $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$.

From definition, $|s|=2^k$ for some $k\in\mathbb{N}$, but $|uv^nw^nx|=|uwx|+n*|vx|$. Suppose $$|uwx|=2^a, |uvwxy|=2^b (b>a)$$ then $$|uv^2wx^2y|=2|uvwxy|-|uwx| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ is not a power of 2, i.e. $uv^2wx^2y\notin L$.

Source Link
Terence Hang
Terence Hang
  • 789
  • 4
  • 7

$L = \{a^{2^k}, k \in \mathbb{N}\}$ is not a context free.language according to Pumping lemma for context-free languages.

Suppose L is context-free, then there exists some integer $p \ge 1$, that every string s in L that $|s| \ge p$ can be written as $s=uvwxy$ where $|vwx|\le p$, $|vx|\ge 1$ and $uv^nwx^ny$ is in $L$ for all $n \ge 0$

From definition, $|s|=2^k$ for some $k\in\mathbb{N}$, but $|uv^nw^nx|=|uwx|+n*|vx|$. Suppose $$|uwx|=2^a, |uvwxy|=2^b (b>a)$$ then $$|uv^2wx^2y|=2|uvwxy|-|uwx| = 2^{b+1}-2^a = 2^a(2^{b+1-a}-1)$$ is not a power of 2. ie. $uv^2wx^2y\notin L$.