Using pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ non-regular - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-20T18:26:36Z https://cs.stackexchange.com/feeds/question/99546 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/99546 0 Using pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ non-regular 1011 1110 https://cs.stackexchange.com/users/81300 2018-11-03T16:57:04Z 2018-11-03T19:53:40Z <p>I'm having issues using the pumping lemma to prove <span class="math-container">$L2 = \{a^ib^j |i &gt; j \}$</span> is non-regular. It's obvious to know that the language is non-regular as there is no way of tracking <span class="math-container">$a^{i's}$</span> and <span class="math-container">$b^{j's}$</span></p> <p>So I've done some digging. On <a href="https://moodle.cs.huji.ac.il/cs12/file.php/67521/Ex3Sol.pdf" rel="nofollow noreferrer">page 2</a> here I found a proof. However, it doesn't make sense to me.</p> <p>Here is the proof, I will list my understandings as we go through the proof:</p> <blockquote> <p>Assume by way of contradiction that <span class="math-container">$L2 ∈ REG$</span>, then <span class="math-container">$L2$</span> satisfies the conditions of the pumping lemma. Let <span class="math-container">$p &gt; 0$</span> be the pumping constant. Consider the word <span class="math-container">$w = a^{p+1}b^p$</span>.</p> </blockquote> <p>Makes complete sense.</p> <blockquote> <p>Clearly <span class="math-container">$w ∈ L2$</span> and <span class="math-container">$|w| &gt; p$</span>, so according to the pumping lemma there exist <span class="math-container">$x, y, z ∈ Σ^∗$</span> such that <span class="math-container">$w = xyz,$</span> <span class="math-container">$|xy| ≤ p,$</span> <span class="math-container">$|y| &gt; 0$</span> and for all <span class="math-container">$i ≥ 0$</span> it holds that <span class="math-container">$xy^iz ∈ L$</span>.</p> </blockquote> <p>Now if an <span class="math-container">$i$</span> is chosen to be <span class="math-container">$0$</span>, this would conflict with <span class="math-container">$|y| &gt; 0$</span>? It seems it's using <span class="math-container">$L$</span> instead of <span class="math-container">$L2$</span>. Is there a reasoning? <br></p> <blockquote> <p>Since <span class="math-container">$|xy| ≤ p$</span>, then <span class="math-container">$x = a^n, y = a^m$</span>, and <span class="math-container">$z = a^kb^{p+1}$</span> such that <span class="math-container">$m + n + k = p$</span>, and <span class="math-container">$m &gt; 0$</span>.</p> </blockquote> <p>This makes sense to me, as <span class="math-container">$z$</span> is equal to the rest of the <span class="math-container">$a's$</span> not in <span class="math-container">$x$</span> and <span class="math-container">$y$</span> plus all the <span class="math-container">$b's$</span>. <br></p> <blockquote> <p>We pump with <span class="math-container">$i = 0$</span> and get the word <span class="math-container">$xz = a^nz = a^na^kb^{p+1}$</span>. Since <span class="math-container">$m+n+k = p+1$</span> and <span class="math-container">$m &gt; 0$</span>, then <span class="math-container">$n+k &lt; p+ 1$</span>.</p> </blockquote> <p><br> Now this doesn't make sense to me. Pumping down ridding of <span class="math-container">$y$</span> contradicts the <span class="math-container">$|y| &gt; 0$</span> rule and how does <span class="math-container">$m+n+k$</span> change to now equal <span class="math-container">$p+1$</span> <br></p> <blockquote> <p>Thus, <span class="math-container">$xz ∉ L1$</span>, in contradiction to the pumping lemma. So <span class="math-container">$L2$</span> is not regular. Note that it is crucial to “pump down” for this language.</p> </blockquote> <p>If you guys can help me understand this proof, that would be great thanks</p> https://cs.stackexchange.com/questions/99546/using-pumping-lemma-to-prove-l2-aibj-i-j-non-regular/99558#99558 1 Answer by xskxzr for Using pumping lemma to prove $L2 = \{a^ib^j |i > j \}$ non-regular xskxzr https://cs.stackexchange.com/users/83244 2018-11-03T19:53:40Z 2018-11-03T19:53:40Z <blockquote> <p>Now if an <span class="math-container">$i$</span> is chosen to be 0, this would conflict with <span class="math-container">$|y|&gt;0$</span>?</p> </blockquote> <p>Note it's <span class="math-container">$|y|&gt;0$</span>, not <span class="math-container">$|y^i|&gt;0$</span>, so there's no problem.</p> <p>All your other confusions come from the typos in the proof. I rewrite the proof (the fixed typos are colored red) as follows.</p> <p>... Clearly <span class="math-container">$w \in L_2$</span> and <span class="math-container">$|w| &gt; p$</span>, so according to the pumping lemma there exist <span class="math-container">$x, y, z \in \Sigma^∗$</span> such that <span class="math-container">$w = xyz,$</span> <span class="math-container">$|xy| \le p,$</span> <span class="math-container">$|y| &gt; 0$</span> and for all <span class="math-container">$i \ge 0$</span> it holds that <span class="math-container">$xy^iz \in L$</span>. Since <span class="math-container">$|xy| \le p$</span>, then <span class="math-container">$x = a^n, y = a^m$</span>, and <span class="math-container">$z = a^kb^\color{red}p$</span> such that <span class="math-container">$m + n + k = \color{red}{p+1}$</span>, and <span class="math-container">$m &gt; 0$</span>. We pump with <span class="math-container">$i = 0$</span> and get the word <span class="math-container">$xz = a^nz = a^na^kb^\color{red}p$</span>. Since <span class="math-container">$m+n+k = p+1$</span> and <span class="math-container">$m &gt;0$</span>, then <span class="math-container">$n+k \color{red}{\le p}$</span> ...</p>