show that the language is non context free example from pg.195 Using an argument

Question

show that the language is non context free

example from pg.195

Using an argument similar to the one on p. 195, show that the language PRIME = {an where p is a prime} is non-context-free. Let us consider the language PRIME = {ap where p is a prime) = {aa aaa aaaaa aaaaaaa . . .} Is PRIME a regular language? If it is, then there is some FA that accepts exactly these words. Let us keep one such automaton in mind. Let us suppose, for the sake of argument, that it has 345 states. Let us choose a prime number bigger than 345-for example, 347. Then a347 can be broken into parts x, y, and z such that xynz is in PRIME for any value of n. The parts x, y, and z are all just strings of a's. Let us take the value of n = 348. By the pumping lemma, the word xy348z must be in PRIME. Now

Explanation / Answer

now first let us assume that P is a prime number.

so a^p is in the given language.

Claim: L is a context free language. so we can apply pumping lemma.

let a^p =uvxyz (we divided our string into 5 substrings)

(if given language is Context free language then if a string s=uvxyz is in language ,then s=u v^n x y^n z for all values of n>=0 must be in the language. if atlest one of those strings is not present then its not a context free language.)

now let v=a^i and y=a^j and let i+j >=1

now we pump the string a^p

----from the pumping lemma we will get...

u.v^(1+p).x.y^(1+p).z     (here we took the value of n as p+1)

(by expanding this expression we get)

(u).( v) . (v^p).( x) .(y).( y^)p.( z)

(by rearrangin this expression we get)

u . v . x. y. z .(v^p) .(y^p)

(as a^p = u.v.x.y.z we get)

a^p..(v^p) .(y^p)

now put v=a^i and y=a^j  

we get

a^p..(a^p.i) .(a^p.j)

finally taking p common in the power we get

a^p(1+i+j)

now even a^p(1+i+j) must be in our language. but that is not possible as p(1+i+j) is not a prime number

so our claim that L is a context free language is False.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.