Babbage Session 2 - 6/3/98
back to home
What is computation? Over the course of the next month we'll discover current models and comprehend them, hopefully in physical terms.
This week we are doing the first8 chapters of Introduction to Automata Theory, Languages, and Computation by Hopcroft and Ullman (H&U). These chapters are generally taught as a semester course, so it is somewhat ambitious to do them in a week. The book is on the shelf in room 022 by the violin area, and is also readily available anywhere fine CS books are sold or leased. Almost every CS undergrad has it on their shelf.
So….presentations this week:
Chapter 1 is a review of some math and notation that may be useful to read. At the end of chapter 1 there is a nice summary of the whole book at the end, which I found very helpful for motivation.
Chapter 2 - Bernd Schoner
Chapter 3 - Ebeth (you will have to read and understand chapt 2 in order to do chapter 3 for sure.)
Chapters 4 & 5 - Yael.
Chapters 6& 7 - Ben
Chapters 8& 9 - Rich
Edward - Pick up where Rich left off after chapter 9, to talk about the highlights of recursion theory a bit and how it fits in with Hopcroft and Ullman.
Some fun things to think about as you read:
1) How could you say all this stuff with matrices?
2) If you had a row of symbols generated by some unknown system and you wanted to characterize the unknown system (a black box), would this theory help you? Hint: If I told you I have a DFA that will accept the string of symbols that comes from the black box, what does it say about the system in the black box? What if I told you I have an NFA that will accept the string? How about Push-down Automata, or a Turing machine?
4) what is a minimal DFA? How can I reduce an ugly DFA to a minimal DFA?
3) Given a string, what algorithm could I follow to construct a/the minimal DFA that would accept this string? Is there always a minimal DFA? Is it unique? How about NFA's?
4) Are DFA's, Pushdown Automata and Turing Machines the only possible types of structures that can exist in this hierarchy? Is the Chomsky hierarchy obvious, unique, and necessary? Could there be something more compelx than a turing Amchine? Simpler than a DFA? Something in between?
5) Extra credit: what does all of this have to do with a metric? Hint: Can an FSA define a metric?
6) what is the relationship between this stuff and so called analog systems ie. Differential Equations or PDE's?
7) extra credit: what would a quantum finite state automata be? How would it differ from the automata described in H&U?
tr. by Ben Vigoda
--------------------------------------------------------------------------------------------------------
Discussion: