Cheap and Secure Web Hosting Provider : See Now

[Answers] Proving a language is not regular with pumping lemma

, , No Comments
Problem Detail: 

I'm having a little bit of an issue with a pumping lemma problem. I've successfully completely all my other problems but this is the last one and I'm a little confused I must say. If anyone can help me out, it'd be much appreciated.

\begin{equation} A = \{a^n b^m c^l \mid n\leq m \vee m\leq l\} \end{equation}

Asked By : Requiem

Answered By : Luke Mathieson

To expand a little on Ran G.'s comment, given a pumping length of $p$, we can take the string $s=a^{p}b^{p} \in A$, then splitting into $s=xyz$, the $y$ section (the part that can be pumped) must be all $a$s, so pumping up leaves us with a string $s'=a^{p+k}b^{p} \notin A$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10461

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback