A Course in Formal Languages, Automata and Groups (Universitext)

A Course in Formal Languages, Automata and Groups (Universitext), 9781848009394 (1848009399), Springer, 2009

This book is based on notes for a master’s course given at Queen Mary, University of London, in the 1998/9 session. Such courses in London are quite short, and the course consisted essentially of the material in the first three chapters, together with a two-hour lecture on connections with group theory. Chapter 5 is a considerably expanded version of this.

For the course, the main sources were the books by Hopcroft and Ullman ([20]), by Cohen ([4]), and by Epstein et al. ([7]). Some use was also made of a later book by Hopcroft and Ullman ([21]). The ulterior motive in the first three chapters is to give a rigorous proof that various notions of recursively enumerable language are equivalent. Three such notions are considered. These are: generated by a type 0 grammar, recognised by a Turing machine (deterministic or not) and defined by means of a G¨odel numbering, having defined “recursively enumerable” for sets of natural numbers. It is hoped that this has been achieved without too many arguments using complicated notation. This is a problem with the entire subject, and it is important to understand the idea of the proof, which is often quite simple. Two particular places that are heavy going are the proof at the end of Chapter 1 that a language recognised by a Turing machine is type 0, and the proof in Chapter 2 that a Turing machine computable function is partial recursive.

The study of formal languages and automata has proved to be a source of much interest and discussion amongst mathematicians in recent times. This book, written by Professor Ian Chiswell, attempts to provide a comprehensive textbook for undergraduate and postgraduate mathematicians with an interest in this developing field. The first three Chapters give a rigorous proof that various notions of recursively enumerable language are equivalent. Chapter Four covers the context-free languages, whereas Chapter Five clarifies the relationship between LR(k) languages and deterministic (context-free languages). Chiswell's book is unique in that it gives the reader a thorough introduction into the connections between group theory and formal languages. This information, contained within the final chapter, includes work on the Anisimov and Muller-Schupp theorems.

Comments

Amazing Books

Intimacy: Clinical, Cultural, Digital and Developmental Perspectives

Routledge, 2018

Intimacy: Clinical, Cultural, Digital and Developmental Perspectives applies a contemporary, psychoanalytic lens to the many facets of intimacy between people, from romantic and sexual relationships, to friendliness, as well as the ways intimacy is mediated by new digital technologies.

Identifying...

SolidWorks 2010: No Experience Required

Sybex, 2010

Whether you are a new user of SolidWorks or a professional who wants to improve your skills, this book was written for you. Learning any software can be difficult at times. You launch the software for the first time, and you feel overwhelmed, not knowing how to even start a new document. In 3D CAD programs, it can be especially difficult....

John Cleland's Fanny Hill: Memoirs of a woman of pleasure

Mayflower, 1970

I sit down to give you an undeniable proof of my considering your desires as indispensable orders. Ungracious then as the task may be, I shall recall to view those scandalous stages of my life, out of which I emerg'd, at length, to the enjoyment of every blessing in the power of love, health, and fortune to bestow; whilst yet in the flower of...

Special Edition Using XML Schema

Que, 2001

The Extensible Markup Language is one of the most controversial technologies to come into vogue in recent years. Starting with humble roots with the desire to create a simple subset of SGML, XML burst onto the scene to a fantastic fanfare from developers and hype from the press. As more people have started to adopt XML, more...

Biomechanics: Principles and Applications, Second Edition

CRC Press, 2007

Engineering is the integration of art and science and involves the use of systematic knowledge based on the principles of mathematics and the physical sciences to design and develop systems that have direct practical applicability for the benefit of mankind and society.With this philosophy in mind, the importance of the engineering...

System Engineering and Automation: An Interactive Educational Approach

Springer, 2011

This book provides insight and enhanced appreciation of analysis, modeling and control of dynamic systems. The reader is assumed to be familiar with calculus, physics and some programming skills. It might develop the reader’s ability to interpret physical significance of mathematical results in system analysis. The book also prepares...