Overview

The study of formal languages and of related families of automata has long been at the core of theoretical computer science. Until recently, the main reasons for this centrality were connected with the specification and analy­ sis of programming languages, which led naturally to the following ques­ tions. How might a grammar be written for such a language? How could we check whether a text were or were not a well-formed program generated by that grammar? How could we parse a program to provide the structural analysis needed by a compiler? How could we check for ambiguity to en­ sure that a program has a unique analysis to be passed to the computer? This focus on programming languages has now been broadened by the in­ creasing concern of computer scientists with designing interfaces which allow humans to communicate with computers in a natural language, at least concerning problems in some well-delimited domain of discourse. The necessary work in computational linguistics draws on studies both within linguistics (the analysis of human languages) and within artificial intelligence. The present volume is the first textbook to combine the topics of formal language theory traditionally taught in the context of program­ ming languages with an introduction to issues in computational linguistics. It is one of a series, The AKM Series in Theoretical Computer Science, designed to make key mathematical developments in computer science readily accessible to undergraduate and beginning graduate students.

Full Product Details

Author:   James Pustejovsky ,  Robert N. Moll ,  Michael A. Arbib ,  A.J. Kfoury
Publisher:   Springer-Verlag New York Inc.
Imprint:   Springer-Verlag New York Inc.
Edition:   Softcover reprint of the original 1st ed. 1988
Dimensions:   Width: 15.50cm , Height: 1.10cm , Length: 23.50cm
Weight:   0.335kg
ISBN:  

9781461395973

ISBN 10:   1461395976
Pages:   203
Publication Date:   02 March 2012
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

1 Introduction.- 1.1 The First Language.- 1.2 Grammers and Languages.- 1.3 Context-Free and Context-Sensitive Languages.- 1.4 Programs, Languages, and Parsing.- 1.5 Context-Free Grammars and Natural Language.- 2 Grammars and Machines.- 2.1 The Chomsky Hierarchy.- 2.2 Closure Properties.- 2.3 Regular and Finite-State Languages.- 3 Push-Down Automata and Context-Free Grammars.- 3.1 Push-Down Automata.- 3.2 Normal Forms for Context-Free Grammars.- 3.3 The Equivalence Theorem.- 4 Parsing, Part 1.- 4.1 The Cocke-Kasami-Younger Algorithm.- 4.2 Earley’s Algorithm.- 5 Turing Machines and Language Theory.- 5.1 Turing Machines.- 5.2 The Universal Turing Machine.- 5.3 Nondeterministic Turing Machines and Linear Bounded Automata.- 5.4 The Halting Problem and Undecidability.- 6 Fixed Point Principles in Language Theory.- 6.1 Partial Orders and Fixed Points.- 6.2 Fixed Point Theory and Context-Free Languages.- 7 Parsing, Part II.- 7.1 Top-Down Parsing and LL Grammars.- 7.2 Bottom-Up Parsing and LR Grammars.- 8 The Formal Description of Natural Languages.- 8.1 The Aims of Linguistic Theory.- 8.2 The Generative Power of Natural Languages.- 8.3 Augmented Transition Networks.- 9 Recent Approaches to Linguistic Theory.- 9.1 Beyond Unrestricted Phrase Structure Formalisms.- 9.2 Generalized Phrase Structure Grammars.- 9.3 Government and Binding Theory.- References for Chapters 8 and 9.- Symbol Index.- Author Index.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions