This page intentionally left blank P1:JsY second CUUS348-Shallit 9780521865722 August6,2008 21:1 ASecondCourseinFormalLanguagesandAutomataTheory Intended for graduate students and advanced undergraduates in computer science, A SecondCourseinFormalLanguagesandAutomataTheorytreatstopicsinthetheory ofcomputationnotusuallycoveredinafirstcourse. Afterareviewofbasicconcepts,thebookcoverscombinatoricsonwords,regular languages,context-freelanguages,parsingandrecognition,Turingmachines,andother language classes. Many topics often absent from other textbooks, such as repetitions inwords,statecomplexity,theinterchangelemma,2DPDAs,andtheincompressibility method,arecoveredhere.Theauthorplacesparticularemphasisontheresourcesneeded torepresentcertainlanguages.Thebookalsoincludesadiversecollectionofmorethan 200exercises,suggestionsfortermprojects,andresearchproblemsthatremainopen. jeffrey shallitisprofessorintheDavidR.CheritonSchoolofComputerScience at the University of Waterloo. He is the author of Algorithmic Number Theory (co- authoredwithEricBach)andAutomaticSequences:Theory,Applications,Generaliza- tions(coauthoredwithJean-PaulAllouche).Hehaspublishedapproximately90articles onnumbertheory,algebra,automatatheory,complexitytheory,andthehistoryofmath- ematicsandcomputing. i P1:JsY second CUUS348-Shallit 9780521865722 August6,2008 21:1 ii P1:JsY second CUUS348-Shallit 9780521865722 August6,2008 21:1 A Second Course in Formal Languages and Automata Theory JEFFREY SHALLIT UniversityofWaterloo iii CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK Published in the United States of America by Cambridge University Press, New York www.cambridge.org Information on this title: www.cambridge.org/9780521865722 © Jeffrey Shallit 2009 This publication is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2008 ISBN-13 978-0-511-43700-7 eBook (EBL) ISBN-13 978-0-521-86572-2 hardback Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. P1:JsY second CUUS348-Shallit 9780521865722 August6,2008 21:1 Contents Preface pageix 1 Reviewofformallanguagesandautomatatheory 1 1.1 Sets 1 1.2 Symbols,strings,andlanguages 1 1.3 Regularexpressionsandregularlanguages 3 1.4 Finiteautomata 4 1.5 Context-freegrammarsandlanguages 8 1.6 Turingmachines 13 1.7 Unsolvability 17 1.8 Complexitytheory 19 1.9 Exercises 21 1.10 Projects 26 1.11 Researchproblems 26 1.12 NotesonChapter1 26 2 Combinatoricsonwords 28 2.1 Basics 28 2.2 Morphisms 29 2.3 ThetheoremsofLyndon–Schu¨tzenberger 30 2.4 Conjugatesandborders 34 2.5 Repetitionsinstrings 37 2.6 ApplicationsoftheThue–Morsesequence andsquarefreestrings 40 2.7 Exercises 43 2.8 Projects 47 2.9 Researchproblems 47 2.10 NotesonChapter2 47 v P1:JsY second CUUS348-Shallit 9780521865722 August6,2008 21:1 vi Contents 3 Finiteautomataandregularlanguages 49 3.1 MooreandMealymachines 49 3.2 Quotients 52 3.3 Morphismsandsubstitutions 54 3.4 Advancedclosurepropertiesofregularlanguages 58 3.5 Transducers 61 3.6 Two-wayfiniteautomata 65 3.7 Thetransformationautomaton 71 3.8 Automata,graphs,andBooleanmatrices 73 3.9 TheMyhill–Nerodetheorem 77 3.10 Minimizationoffiniteautomata 81 3.11 Statecomplexity 89 3.12 Partialordersandregularlanguages 92 3.13 Exercises 95 3.14 Projects 105 3.15 Researchproblems 105 3.16 NotesonChapter3 106 4 Context-freegrammarsandlanguages 108 4.1 Closureproperties 108 4.2 Unarycontext-freelanguages 111 4.3 Ogdens’lemma 112 4.4 ApplicationsofOgdens’lemma 114 4.5 Theinterchangelemma 118 4.6 Parikhs’theorem 121 4.7 Deterministiccontext-freelanguages 126 4.8 Linearlanguages 130 4.9 Exercises 132 4.10 Projects 138 4.11 Researchproblems 138 4.12 NotesonChapter4 138 5 Parsingandrecognition 140 5.1 Recognitionandparsingingeneralgrammars 141 5.2 Earleys’method 144 5.3 Top-downparsing 152 5.4 RemovingLL(1)conflicts 161 5.5 Bottom-upparsing 163 5.6 Exercises 172 5.7 Projects 173 5.8 NotesonChapter5 173 P1:JsY second CUUS348-Shallit 9780521865722 August6,2008 21:1 Contents vii 6 Turingmachines 174 6.1 Unrestrictedgrammars 174 6.2 Kolmogorovcomplexity 177 6.3 Theincompressibilitymethod 180 6.4 Thebusybeaverproblem 183 6.5 ThePostcorrespondenceproblem 186 6.6 Unsolvabilityandcontext-freelanguages 190 6.7 Complexityandregularlanguages 193 6.8 Exercises 198 6.9 Projects 200 6.10 Researchproblems 200 6.11 NotesonChapter6 200 7 Otherlanguageclasses 202 7.1 Context-sensitivelanguages 202 7.2 TheChomskyhierarchy 212 7.3 2DPDAsandCooks’theorem 213 7.4 Exercises 221 7.5 Projects 222 7.6 Researchproblems 222 7.7 NotesonChapter7 223 Bibliography 225 Index 233 P1:JsY second CUUS348-Shallit 9780521865722 August6,2008 21:1 viii