CODEWITHSUNDEEP
automata
Moe
Moe

Reputation: 65

Prove that the languages are not context free?

How can I prove the following language is not context-free? Any help will be appreciated. Thank you. L = {0^n| n is a prime}

Upvotes: 1

Views: 431

Answers (1)

Patrick87
Patrick87

Reputation: 28292

The proof is by contradiction. Assume the language is context-free. Then, by the pumping lemma for context-free languages, any string in L can be written as uvxyz where |vxy| < p, |vy| > 0 and for all natural numbers k, u(v^k)x(y^k)z is in the language as well. Choose 0^m where m is any prime > p. Then we must be able to write 0^m as uvxyz so that |vy| > 0. Let |vy| = r. Then 0^(m-r+kr) must be prime for any natural number k. However, choosing k=m+1 gives m-r+(m+1)r = m - r + mr + r = m(1 + r) which cannot be prime, a contradiction. Therefore, our assumption that the language is context-free is disproven.

Upvotes: 1

Related Questions