<A Concise Introduction to Languages and Machines>
Part I languages and machines
1. elements of formal languages
1.1 overview
[discuss]:
⁃ building blocks of formal languages: alphabets and strings
⁃ grammars and languages
⁃ Chomsky hierarchy: a way of classifying grammars and languages
⁃ relationships between formal languages and programming language definition
[introduce]:
⁃ writing definitions of sets of strings
⁃ producing sentences from grammars
⁃ using notations of formal languages
1.2 alphabets
1.3 strings
⁃ functions that apply to strings
⁃ notations for describing strings
1.4 formal languages
1.5 methods of defining formal languages
⁃ set definitions of languages
⁃ decision programs for languages
⁃ rules for generating languages
1.6 formal grammars
⁃ grammars, derivations and languages
⁃ the relationships between grammars and languages
1.7 phrase structure grammars and Chomsky hierarchy
⁃ formal definitions of phrase structure grammars
⁃ derivations, sentential forms, sentences, and L(G)
⁃ the Chomsky hierarchy
1.8 a type-0 grammar: computation as symbol manipulation
2. syntax, semantics and ambiguity
2.1 overview
2.2 syntax vs. semantics
2.3 derivation trees
2.4 parsing
2.5 ambiguity
3. regular languages and finite state recognizers
3.1 overview
3.2 regular grammars
3.3 some problems with grammars
3.4 Finite state recognizers and generators
3.5 non-determinism in finite state recognizers
3.6 a simple deterministic decision program
3.7 minimal FSRs (Finite State Recognizers)
3.8 the general equivalence of regular languages and FSRs
3.9 observations on regular grammars and regular languages
4. context free languages and pushdown recognizers
4.1 overview
4.2 context free grammars and context free languages
4.3 changing G without changing L(G)
4.4 pushdown recognizers
4.5 deterministic pushdown recognizers
4.6 deterministic and non-deterministic context languages
4.7 the equivalence of CFGs and PDRs
4.8 observations on context free grammars and languages
5. important features of regular and context free languages
5.1 overview
5.2 closure properties of languages
5.3 closure properties of the regular languages
5.4 closure properties of context free languages
5.6 Chomsky’s hierarchy is indeed a proper hierarchy
5.7 preliminary observations on the scope of the Chomsky’s hierarchy
6. phrase structure languages and Turing machines
6.1 overview
6.2 the architecture of the Turing machine
6.3 the behaviour of a Turing machine
6.4 Turing machines as language recognizers
6.5 introduction to computable languages in terms of TM
6.6 the TM as the recognizer for the context sensitive languages
6.7 the TM as the recognizer for the type-0 languages
6.8 decidability: a preliminary discussion
6.9 end of part one
Part II machines and computation
7. finite state transducers
8. Turing machines as computers
9. Turing’s thesis and universality of the Turing machine
10. computability, solvability and halting problem
11. dimensions of computation
further readings
Church (1936) An unsolvable problem of elementary number theory
Cohen (1996) Introduction to computer theory
Floyd and Beigel (1994) The language of machines: an introduction to computability and formal languages
Harel (1992) Algorithmics: the spirit of computing
Harrison (1978) Introduction to formal language theory
Hopcroft and Ullman (1979) Introduction to automata theory, languages and computation
Jensen and Wirth (1975) Pascal user manual and report
Kain (1972) Automata theory: machines and languages
Kelly (1998) Automata and formal languages: an introduction
Minsky (1967) Computation: finite and infinite machines
Post (1936) Finite combinatory processes
Rayward-Smith (1983) A first course in formal language theory
Rich and Knight (1991) Artificial intelligence
Tanenbaum (1998) Computer networks
Turing (1936) On computable numbers with an application to the Entscheidungsproblem
Winston (1992) Artificial Intelligence
Wood (1987) Theory of computation
· · · · · · (收起)