-1
$\begingroup$

enter image description here

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be appreciated.

I understand that the string has to have a length greater than the pumping length of L. What does that even mean in this context of such a vast alphabet?

I imagine I have to choose a string that fits the properties:

must be in the form of the expression a+b=c no leading zeros in a,b,c the expression on the left must equal the value on the right But I do not know what string would fit all these properties but also provides a contradiction in the proof.

My Attempt:

enter image description here

Improve this question
$\endgroup$
1
  • $\begingroup$ Sorry but, as the description of the "check my answer" tag makes clear, questions asking us to check answers to problems are off-topic, here. They're only ever useful to the person whose work we're being asked to grade, whereas we're looking to build up a repository of generally useful questions and answers. Commenting on your work is your professor or TA's job. $\endgroup$
    – David Richerby
    Nov 1, 2018 at 18:30

1 Answer 1

Reset to default
0
$\begingroup$

You have demonstrated a pretty good understanding of the pumping lemma for regular languages. Your proof is clean and correct. (That mino typo, $xy^{iz}$ where $z$ should not be in the superscript, could be ignored by a human reader.)

Here is a minor suggestion. You can just use a specific string such as $1^p+2^p=3^p$, instead of a more general one $a^p+b^p=c^p$. Your proof will become easier to write and easier to understand.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Please note that questions of the form "Here's my answer to an exercise: is it correct?" are considered off-topic, here, as the description of the "check my answer" tag makes clear. $\endgroup$
    – David Richerby
    Nov 1, 2018 at 18:29
  • $\begingroup$ Yes, I did notice that. I did read that tag description which said plainly "off-topic". I should have removed that tag from the question. I should have reminded the questioner what is right attitude and right way to write a question. The questioner did put a lot of work into the problem as well as explaining he or she was puzzled. That was why I answered the question. I could have asked he/she where he/she was puzzled. It turned out all he/she needed was some kind of confirmation (which is, indeed, rather useless for future readers). It should help he/she, though. $\endgroup$
    – John L.
    Nov 1, 2018 at 19:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.