World's most popular travel blog for travel bloggers.

[Solved]: Proof that a given language is not context-free

, , No Comments
Problem Detail: 

Given the language $L = \{w \in \{a,b\}^* \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ and the assignement to proof that $L \notin CFL$ with the Pumping lemma.

Assuming $L \in CFL$, would it be possible to start with defining a language $L' := L \cap a^+$ which has to be context-free since $CFL$ is closed under intersection with $REG$. Now I would have to proof that $L' = \{w \in a^+ \, | \, |w| = n \cdot \sqrt{n} \text{ and } n \geq 42\}$ isn't regular because the alphabet contains only one symbol.

Let $k$ be the constant of the Pumping lemma and $m > k$ and $m > 42$. So $z = a^{m^2\cdot\sqrt{m^2}} = a^{m^3} \in L'$.

$|z| = |uvw| = m^3 ...$

How to continue?

Asked By : PeterMcCoy

Answered By : Rick Decker

You're off to a good start. You recognize that all you have to do is show that the language $L'$ isn't regular. You let $k$ be the integer of the PL and choose an integer $m$ with $m>k$ and $m>42$ so you choose to pump the string $z=a^{m^3}$. Write this as $uvw$ with $|v|=t$ and $0<t<k$. Now we'll have $|uv^2w|=m^3+t<m^3+m$. This string can't be in $L'$ since it's strictly smaller than the next largest string in $L'$, namely the one with length $(m+1)^3$, since obviously $$ m^3+m<m^3+3m^2+3m+1 $$ Since $L'$ isn't regular, $L$ can't be a CFL.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48256

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback