An introduction to formal language theory. With contributions by James Pustejovsky (Q4040439)

The starting point for formal language theory (FLT) was the N. Chomsky's attempt to formally describe the natural language (NL) syntactic structures. The theory proved very useful to the programming languages (PL) design, compiler construction, abstract machine theory, etc. In the last decade an (apparently) surprising fact happened: The FLT came more and more to its roots, to NL description. This is, mainly, because the artificial intelligence researches lightened the real essence of computing: the modelling and simulation of the human cognitive processes, whose 'turn-table' is the NL ! The present book has the following basic features: (a) it addresses the undergraduate and beginning (computer science/\(computational\) linguistics) students; (b) even as it is selfcontained, the same authors (optionally) complete the textbook with material from their prior books in the same series of Springer-Verlag [A basis for theoretical computer science (1981; Zbl 0471.68002); A programming approach to computability (1982; Zbl 0497.68025)]; (c) it is the first textbook combining a classical FLT introduction in both application areas: PL and NL. Its last two chapters, written by James Pustejovsky, comprise a very lucid introduction to the new linguistic theories and NL tools. Short hints on the (first seven chapters) book contents: in an extremely clear instructive and concise manner, the authors review all the important resuls on FLT and connected fields: The properties of regular, context- free and context-sensitive languages, their relationship to abstract machines, complexity, (two chapters on) parsing theory. This book, preserving the traditional line of FLT approaches coming from its intensive applications to PL, wonderfully began to recuperate and integrate the valuable achievements from the other main branch: the NL. This reflects the growing importance of computational linguistics in the context of artificial intelligence (thus computer science) in the last two decades. We dare to believe that this trend will strongly continue.