+612 9045 4394
 
CHECKOUT
Automata and Languages : Theory and Applications - Alexander Meduna

Automata and Languages

Theory and Applications

Paperback

Published: 17th July 2000
Ships: 5 to 9 business days
5 to 9 business days
$248.20
or 4 easy payments of $62.05 with Learn more

Automata and Languages presents a step-by-step development of the theory of automata, languages and computation. Intended to be used as the basis of an introductory course to this theory at both junior and senior levels, the text is organized in such a way as to allow the design of various courses based on selected material. Areas featured in the book include:- * basic models of computation * formal languages and their properties * computability, decidability and complexity * a discussion of the modern trends in the theory of automata and formal languages * design of programming languages, including the development of a new programming language * compiler design, including the construction of a complete compiler Alexander Meduna uses clear definitions, easy-to-follow proofs and helpful examples to make formerly obscure concepts easy to understand. He also includes challenging exercises and programming projects to enhance the reader's comprehension, and, to put the theory firmly into a 'real world' context, he presents lots of realistic illustrations and applications in practical computer science.

Introductionp. 1
Mathematical Backgroundp. 3
Setsp. 3
Relationsp. 7
Graphsp. 11
Proofsp. 15
Exercisesp. 18
Languagesp. 25
Formalization of languagesp. 25
Expressions and grammarsp. 33
Expressionsp. 33
Grammarsp. 34
Specification of a programming languagep. 39
Translationsp. 48
Exercisesp. 52
Programming Projectsp. 57
Automatap. 59
Conceptualization of automatap. 59
Transducersp. 71
Computabilityp. 78
Exercisesp. 82
Programming Projectsp. 88
Bibliographic notesp. 90
Regular Languagesp. 91
Models for Regular Languagesp. 93
Regular expressionsp. 93
Finite automatap. 99
Basic definitionsp. 99
Elimination of [varepsilon]-movesp. 122
Determinismp. 145
Simplificationp. 156
Minimizationp. 171
Finite Automata and regular expressionsp. 175
From regular expressions to finite automatap. 175
Conversion of regular expressions to finite automatap. 175
Scanningp. 196
From finite automata to regular expressionsp. 209
Equivalence of finite automata and regular expressionsp. 219
Exercisesp. 220
Programming projectsp. 227
Properties of Regular Languagesp. 229
Pumping lemmap. 229
Closure propertiesp. 237
Decidable problemsp. 250
Exercisesp. 259
Bibliographic notesp. 265
Context-Free Languagesp. 267
Models for Context-Free Languagesp. 269
Context-free grammarsp. 269
Basic definitionsp. 269
Ambiguityp. 299
Simplificationp. 305
Elimination of useless symbolsp. 305
Elimination of [varepsilon]-productionsp. 321
Elimination of unit productionsp. 334
Proper context-free grammarsp. 346
Normal formsp. 347
Chomsky normal formp. 348
Greibach normal formp. 357
Pushdown automatap. 381
Basic definitionsp. 381
Extensionp. 415
Determinismp. 432
Pushdown automata and context-free grammarsp. 441
From context-free grammars to pushdown automatap. 442
Conversion of context-free grammars to pushdown automatap. 442
Parsingp. 477
From pushdown automata to context-free grammarsp. 486
Equivalence of pushdown automata and context-free grammarsp. 494
Exercisesp. 495
Programming projectsp. 508
Properties of Context-Free Languagesp. 511
Pumping lemmap. 511
Closure propertiesp. 528
Decidable problemsp. 551
Exercisesp. 558
Special Types of Context-Free Languages and Their Modelsp. 565
Deterministic context-free languagesp. 565
Linear and regular grammarsp. 574
Exercisesp. 599
Bibliographic notesp. 605
Beyond Context-Free Languagesp. 607
Generalized Modelsp. 609
Turing machinesp. 609
Basic definitionsp. 609
Determinismp. 631
Simplificationp. 643
Extensionp. 652
Universalityp. 674
Turing machines that always haltp. 693
Linear-bounded automatap. 695
Two-pushdown automatap. 696
Basic definitionsp. 696
Determinismp. 704
Equivalence of two-pushdown automata and Turing machinep. 705
Unrestricted grammarsp. 707
Basic definitionp. 708
Equivalence of unrestricted grammars and Turing machinesp. 713
Normal formsp. 722
Context-sensitive grammarsp. 729
Basic definitionp. 730
Context-sensitive grammars and linear-bounded automatap. 732
Context-sensitive languages and recursive languagesp. 735
Normal forms of context-sensitive grammarsp. 740
Hierarchy of language familiesp. 742
Exercisesp. 743
Programming projectsp. 753
Bibliographic notesp. 755
Translationsp. 757
Finite and Pushdown Transducersp. 758
Finite transducersp. 758
Translation grammars and pushdown transducersp. 770
Translation grammarsp. 770
Pushdown transducersp. 776
Compilersp. 787
Compiler structurep. 788
Scannerp. 789
Parser, semantic analyzer, and code generatorp. 806
Optimizerp. 818
Executionp. 820
Exercisesp. 822
Programming projectsp. 832
Turing Transducersp. 833
Basic definitionsp. 833
Computabilityp. 845
Computersp. 845
Computable functionsp. 851
Uncomputable functionsp. 853
Decidabilityp. 856
Decision makersp. 856
Decidable problemsp. 860
Computational complexityp. 861
Time complexityp. 862
Space complexityp. 866
Undecidable problemsp. 867
Undecidability: a general approachp. 872
Exercisesp. 874
Programming projectsp. 884
Bibliographic notesp. 886
Bibliographyp. 889
Indicesp. 901
Index to Special Symbolsp. 903
Index to Decision Problemsp. 905
Index to Algorithmsp. 907
Subject Indexp. 911
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9781852330743
ISBN-10: 1852330740
Audience: General
Format: Paperback
Language: English
Number Of Pages: 916
Published: 17th July 2000
Publisher: Springer London Ltd
Country of Publication: GB
Dimensions (cm): 23.29 x 15.85  x 5.0
Weight (kg): 1.36