Question number two only Use the pumping lemma to show that

Question number two only

Use the pumping lemma to show that the following language is not context-free L_1 = {0^n 1^n 0^n 1^n | c greaterthanorequalto 0}. L_1 = {a_n b_m | n and m are both prime numbers}.

Solution

Answer 5:

Part 2) The pumping lemma gives you a p

We give a word s of the language of length at least p

The pumping lemma rewrites it like this: s=uvxyz with some conditions (|vxy|p and |vy|1)

You give an integer n0

If uv n xy n z is not in L, you win, L is not context free

Let s=uvxyz , then |s|=|uvxyz|=|u|+|v|+|x|+|y|+|z|

Now for any n we have: |uv n xy n z|=|u|+n|v|+|x|+n|y|+|z|

=|u|+|x|+|z|+n(|v|+|y|) |uvnxynz|

=|u|+n|v|+|x|+n|y|+|z|

=|u|+|x|+|z|+n(|v|+|y|)

Setting n=|u|+|x|+|z| gives us |u|+|x|+|z|+(|u|+|x|+|z|)(|v|+|y|) = (|u|+|x|+|z|)(|v|+|y|+1)

Now if we pick s such that |s| is a prime number strictly larger than the pumping length, and such that |uz|2, we get that |u|+|x|+|z| 2 furthermore, |vy| 1 and thus |v|+|y|+1 2

which implies that |uv n xy n z| is composite, and thus not prime.

Let p be the pumping length guaranteed by the pumping lemma (for context free languages). Then we choose mn such that m,np and are both prime. Then clearly s=a n b m L .

By the pumping lemma we can divide s such that s=uvxyz and |vxy|p   |vy|0

s =uv i xy i zL for all iN

For this language we get three similar cases, and one trivial case. The trivial case is where either v or ycontains both a \'s and b \'s, in which case s    doesn\'t have the correct ordering, and thus s L .

The nontrivial cases:

v and y are both strings of a \'s, then when we pump s we get s = a n+ik b n   where k1 Then s L ifgcd(n+ik,m) =1 , however the modular equation n+ik0(m) has the solution i nk 1 (m) , and as m is prime we are guaranteed that k 1   exists.

Therefore any element of the residue class i nk 1 (m) would give us gcd(n+ik, m) > 1 . Ergo s L .Short version: we can pump the string so that n+ik is a multiple of m for any k with 1 k p < m,n (which is what we set up at the start). v and y are both strings of b \'s, but this case is just the symmetric case to case 1, so we derive a contradiction in this case too.

v=ak   and y=b h   for some k and h with 1k+hp . Then when we pump we get s =a n+ik b m+ih  .

Now s L if n+ik m+ih(m) has no solution, but as I\'m sure you can see from here, rearranging just gives n+i(k+h) 0(m) , and as before this has solution i n(k+h) 1 (m) . So again we derive a contradiction.