|
Java has some unusual features that set it apart from most traditional
programming languages. The most striking may be that while it is a
compiled language, the resulting object code is not designed for any
particular platform; rather, it is meant to run on a Java Virtual
Machine (JVM), which does not physically exist in the form of a real,
tangible machine (yet). Thus, to run java programs on other machines,
you must first execute the JVM program that has been compiled for your
particular system, then run the java program on the JVM. The Java Development Kit (JDK) is a huge conglomeration of nifty tools, libraries, documentations, and all sorts of other technical goodies, all geared towards allowing you to develop java programs. The latest version of the JDK can be downloaded from www.javasoft.com . The most important tools are javac and java, but you may also find yourself using javadoc, jdb, and appletviewer on occasion. java is the JVM program. All java programs are run by invoking java first; e.g., "java myprog". javac is the compiler which will take your *.java source code and create the *.class object code. Note a very interesting feature of javac: it has a built-in make facility, so you don't have to explicitly compile all your *.java files; instead, you just compile the one containing main(), and all other needed files get compiled automatically. While you are not required to use them, the other programs in the JDK may be useful to you. Briefly: javadoc scans your source code and builds up an HTML document of your classes; jdb is the debugger; and appletviewer lets you run java applets without invoking it through a browser. Feel free to experiment with them all.
|
|
I'm sure you've encountered proofs by contradiction before. Note that
using the pumping theorem to show a language is not regular is in fact
a proof by contradiction: the theorem states some property which all
regular languages must have, so given some language that you wish to
prove as being not regular, you first assume that it is, then you show
that if you try to pump it, you fail. Note that this points out clearly one mistake that is very tempting (but very wrong) to make: you cannot use the pumping theorem as a tool for proving that some language is regular. Why? When showing that a language L is regular, there's no contradiction to draw upon when using the pumping theorem, since L is pumpable. The pumping property must hold for all regular languages, but it can also hold for some non-regular languages as well; in other words, the pumping property is a necessary but NOT sufficient condition for regular languages. When doing proofs by contradiction, make sure you create as airtight an argument as possible. In homework #3, in the problem that asks you to prove that you cannot have less than 2n states in the DFA that accepts L = { w in {a,b}* : the nth character from the right is an a }. It is not enough just to show that there are 2n states that result when you do the NDFA-to-DFA construction, because some critic might then ask why it's not possible that some of those states might not be needed, and why it's not possible that some of those states might be the same state. Thus, you must address the issues of necessity and uniqueness. Often, in a contradiction proof, the most convincing evidence you can produce is a counterexample. Thus, you assume that you can construct a DFA of less than 2n states, then you come up with examples of strings that are definitely not in L but must be accepted by this DFA. At this point, you should notice that the weakness that you are aiming for is the fact that there are less states than there are unique strings, which should in turn shift your thoughts toward the pigeonhole principle. The states are your pigeonholes, and the strings are your pigeons; the rest of the proof then falls out with just a little more thought.
|