Question

Use the Pumping Lemma to show that the following languages are not regular.

(a){a^pa^q | for all integers p and q where q is a prime number and p is not prime}.

(b) {aⁱ b^j || i − j | = 3}

(c) {aⁱ b^j c^k | i = j or j 6= k}

(d) {aⁱb^j | i/j is an integer}

Answer 1

I'll add them in few minutes! Please wait..

These kind of problems are solved using proof by contradiction method. At the first the languages are assumed to be regular, then taking at least one string that conforms to the language which is assumed regular but thence is shown to be non-regular which suffices that the language is non-regular and our assumption was wrong. In the following, I'll attach the proof of those parts on-by-one. g Lemma for Regular Languages L say that there exists a pumping length p for L such tthat for any string s E L where l: p, s= xyz subject to: 1. yl> 0 Then we have to choose proper x, y, z and proceed with intention of proving at least one string s which is neither regular nor following the rules of L, but s EL. This will do the trick. Following are the snapshots for proof.