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 thecontext-free languages, whereas Chapter Five clarifies the relationship between LR(k) languages and deterministic (context-free languages). Chiswell's bookis 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. A rigorous proof of the equivalence of various notions of recursively enumerable and recursive languages A proof is included of the result of Muller and Schupp A full proof is given of the connection between LR(k) languages and languages recognised by deterministic pushdown stack automata Some minor variations in the usual treatment of the world problem for groups, such as the use of generalised sequential machines INDICE: Preface.- Contents.- 1. Grammars and Machine Recognition.- 2. Recursive Functions.- 3. Recursively Enumerable Sets and Languages.- 4. Context-free language.- 5. Connections with Group Theory.- A. Results and Proofs Omittedin the Text.- B. The Halting Problem and Universal Turing Machines.- C. Cantor's Diagonal Argument.- D. Solutions to Selected Exercises.- References.- Index.
- ISBN: 978-1-84800-939-4
- Editorial: Springer
- Encuadernacion: Rústica
- Páginas: 170
- Fecha Publicación: 01/12/2008
- Nº Volúmenes: 1
- Idioma: Inglés