A Concise Introduction to Languages and Machines pdf epub mobi txt 電子書 下載2025

想要找書就要到 小美書屋

立刻按 ctrl+D收藏本頁

你會得到大驚喜!!

This book focuses on key theoretical topics of computing, in particular formal languages and abstract machines. It is intended primarily to support the theoretical modules on a computer science or computing-related undergraduate degree scheme.

Though the book is primarily theoretical in nature, it attempts to avoid the overly mathematical approach of many books on the subject and for the most part focuses on encouraging the reader to gain an intuitive understanding. Proofs are often only sketched and, in many cases, supported by diagrams. Wherever possi- ble, the book links the theory to practical considerations, in particular the implications for programming, computation and problem solving.

For Students

I wrote this book partly because when I studied this material as part of my own Computing degree, I had to work really hard to understand the material, a situation which arose not because the material is too difficult, but because it was not well presented and the books seemed to assume I was a pure mathema- tician, which I am not.

This book is primarily for undergraduate students of computing, though it can also be used by students of computational linguistics and researchers, particularly those entering computer science from other disciplines, who find that they require a foundation or a refresher course in the theoretical aspects of computing.

Some aspects of the book are certainly clearer if the student has some experi- ence of programming, though such experience is not essential for understanding most of the book.

The reader is advised where especially demanding material can be omitted, though he or she is encouraged to appreciate the implications of that material, as such an appreciation may be assumed later in the book.

<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
· · · · · · (收起)