In the proof, S is constructed to decide the acceptance problem by constructing Turing machine M2, an encoding of which is then fed to the assumed decider R for REGULARTM. M2 is constructed to accept a particular nonregular language, or to accept if M accepts w (the acceptance problem). When R is run on <M2>, it will reject only when M does not accept w because the union of a nonregular language with all strings is a regular language (sigma star).
Email: Richard dot J dot Wagner at gmail dot com
notes07a.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by
Rick Wagner. Copyright © 1998-2011, all rights reserved.