What is the difference between absurd reasoning and contraposal reasoning? To show that a language is not regular

  • $\begingroup$ What's the context in which you encountered these terms? Can you tell us more? $\endgroup$ – D.W. Dec 13 '17 at 6:13
  • $\begingroup$ I saw in different exercises, to shiw that a language is not regular we can use absurd reasoning or contraposal reasoning... $\endgroup$ – SARR Dec 13 '17 at 17:18
  • $\begingroup$ Ex for L=anbn.... People use absurd or contraposal... I want to know the difference with this two cases. $\endgroup$ – SARR Dec 13 '17 at 17:19

I've never heard those terms in the context of computer science. When you mention "contraposal reasoning", I've never heard that term before, but I suspect that might be a reference to proving the contrapositive. When you mention "absurd reasoning", I've never heard anyone use that specific phrase, but I suspect you might be referring to proof by contradiction, also known as reductio ab absurdum, which is Latin for reduction to absurdity.

These are general proof techniques. They're not specific to showing that a language is not regular.

General advice: I recommend that you try to avoid proof by contradiction. It's a valid proof technique, but my experience is that it often leads beginners awry and causes them to make mistakes in the proof. I recommend instead proving the contrapositive; it leads to more straightforward proofs where it is easier to avoid errors, and spot where you went wrong if you do make an error.

| cite | improve this answer | |
  • $\begingroup$ RAA in the form of "if $P$ holds then we can derive a contradiction, therefore $\not P$ holds" is fine. That's how you prove a negative statement like "$L$ is not a regular language". This case, however, is almost always conflated with "if $\not P$ holds then we can derive a contradiction, therefore $P$ holds", which is what "proof by contradiction" often refers to and I agree this form of reasoning should be avoided,. This applies to proofs that use $(\neg P\to\neg Q)\to(Q\to P)$ too (but not the converse). Many CS results are amenable to constructive proofs which are clearer. $\endgroup$ – Derek Elkins left SE Dec 14 '17 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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