Web Links for Chapter 10

Section 10.1 Languages and Grammars

Page 634

A biography of Chomsky can be found at

http://rafale.worldnet.net/~abdel/linguistics/chomsky.htm (Chomsky)

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

http://cui.unige.ch/db-research/Enseignement/analyseinfo/AboutBNF.html

You can see a photograph of Peter Naur and a photograph of Backus at

http://ei.cs.vt.edu/~history/NaurHOPL.GIF

and

http://ei.cs.vt.edu/~history/Backus.GIF

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

http://tech-www.informatik.uni-hamburg.de/applets/java-fsm/index.html (Java FSM)

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

http://iamexwiwww.unibe.ch/studenten/mguenter/demos/Antenna/index.html (Finite State Simulator)

Page 648

A biography and photograph of Stephen Kleene can be found at

http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Kleene.html (MacTutor History of Mathematics Archive, University St Andrews, Scotland)

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.)

http://theory.uwinnipeg.ca/CPAN/data/DFA-Kleene/Kleene.html (DFA::Kleene)

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.

http://www.turing.org.uk/turing/ (Alan Turing Home Page)

A biography and photograph of Alan Turing can be found at

http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Turing.html (MacTutor History of Mathematics Archive, University St Andrews, Scotland)

Section 10.5. Turing Machines

Page 672

A biography and photograph of Alonzo Church can be found at

http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Church.html (MacTutor History of Mathematics Archive, University St Andrews, Scotland)

Page 673

Information about busy beaver Turing machines can be found at Michael Somos’s page

http://grail.cba.csuohio.edu/~somos/bb.html (Busy Beaver Turing Machine)

Another excellent site that presents the currently best known results about busy beaver Turing machines is found at Heiner Marxen’s page

http://www.drb.insel.de/~heiner/BB/index.html (Heiner Marxen – Busy Beaver)






Copyright ©2001 The McGraw-Hill Companies.
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of the The McGraw-Hill Companies.