Web Links for Chapter 10
Section 10.1 Languages and Grammars
Page 634
A biography of Chomsky can be found at
You can find Noam Chomsky’s home page, containing his photograph, address, and a list of some recent publications at
http://web.mit.edu/linguistics/www/chomsky.home.html
(Noam Chomsky Home Page)Page 637
More information about Backus Naur Form (BNF) taken from M. Marcotty & H. Ledgard, The World of Programming Languages, Springer-Verlag, Berlin 1986., pages 41+ and the BNF lists defining the grammars of a variety of programming languages, including Java, SQL, and LISP, can be found at
You can see a photograph of Peter Naur and a photograph of Backus at
and
respectively.
Section 10.2 Finite-State Machines with Output
Page 640
You can edit and stimulate the actions of finite-state machines with output using Java applets written by Karola Krönert and Ulrich Dallmann of the Computer Science Department of the University of Hamburg, Germany. These applets can be found at
The JavaFSM applet provides an interactive editor and simulator of finite-state machines. The applet supports both Mealy- and Moore-machines. Unfortunately, documentation is currently available only in German (but you can try automatic translation of this by putting this URL as input to the Altavista translation service.
Section 10.3 Finite-States Machines with No Output
Page 647
A simulator of a finite state machine (without output) can be found at the Finite State Simulator site. This simulator allows a user to create and/or modify a finite state machine by adding and/or deleting states and transitions and marking states as initial and/or accepting and to see when an input string chosen by the user is accepted. (The simulator can handle up to 10.) The simulator can be found at
Page 648
A biography and photograph of Stephen Kleene can be found at
Page 650
You can download a module written in Perl from the Comprehensive Perl Archive Network (CPAN) that you can use to define a finite-state machine and to determine the language accepted by this machine. The output consists of a list of regular expressions describing the same language accepted by your finite-state machine. (The module to be downloaded is DFA-Kleene-1.0.tar.gz, which is in a compressed and packaged format. If your system cannot handle unpacking this automatically, consult a book on UNIX to see how to do this.)
Section 10.4. Language Recognition
Page 665
The Alan Turing Home Page contains a wealth of information about Alan Turing, including biographical information, a photo, information about his mathematical work, his cryptographic work, his pioneering work in computer science, and other matieral.
A biography and photograph of Alan Turing can be found at
Section 10.5. Turing Machines
Page 672
A biography and photograph of Alonzo Church can be found at
Page 673
Information about busy beaver Turing machines can be found at Michael Somos’s page
Another excellent site that presents the currently best known results about busy beaver Turing machines is found at Heiner Marxen’s page