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.