# An Introduction to Formal Languages and Automata, 5th Edition

Language: English

Pages: 437

ISBN: 144961552X

Format: PDF / Kindle (mobi) / ePub

Written to address the fundamentals of formal languages, automata, and computability, An Introduction to Formal Languages and Automata provides an accessible, student-friendly presentation of all material essential to an introductory Theory of Computation course. It is designed to familiarize students with the foundations and principles of computer science and to strengthen the students' ability to carry out formal and rigorous mathematical arguments. In the new Fifth Edition, Peter Linz continues to offer a straightforward, uncomplicated treatment of formal languages and automata and avoids excessive mathematical detail so that students may focus on and understand the underlying principles. In an effort to further the accessibility and comprehension of the text, the author has added new illustrative examples and exercises throughout. There is a substantial amount of new material in the form of two new appendices, and a CD-ROM of JFLAP exercises authored by Susan Rodger of Duke University. The first appendix is an entire chapter on finite-state transducers. This optional chapter can be used to prepare students for further related study. The second appendix offers a brief introduction to JFLAP; an interactive software tool that is of great help in both learning the material and in teaching the course. Many of the exercises in the text require creating structures that are complicated and that have to be tested for correctness. JFLAP can greatly reduce students’ time spent on testing as well as help them visualize abstract concepts. The CD-ROM that accompanies every new printed copy expands this and offers exercises specific for JFLAP. (Please note, ebook version does not include the CD-ROM) Instructor Resources: -Instructor Manual -PowerPoint Lecture Outlines

conclusion. 17. Consider the following modification of Definition 2,6. An nfa with multiple initial states is defined by the quintuple M :-(Q,E,d,Qo,F), where 8o C Q is a set of possible initial states. The language accepted by such an automaton is defined as L (M) : {tr.' : d* (q6,trr) contains gy, for any q0 € Qo,St € F} . Show that for every nfa with multiple initial states there exists an nfa with a single initial state that accepts the same language. Nft 18. Suppose that in Exercise 17 we

X,,)' 96,i-) be a 'Ihen ther tlfrr, dfa that accepts tr1. M : ( Q , X , d ,( 0 , Q - F ) accepls Zr. fnis is rather strariglrtforwa,r'd;we havc already slggcstcrd Lhe result irr Exercise 4 in Scrtion 2.1. Noter tltat in the defirritiotr of a' dftr., d* to be n total function, so that d* (qu,rrr) is deliled fbr all we a,ssrrrnecl tr € E*. Cotrsequentlyeitlrt:r d* (qo,u) is a final state, in which caseru € tr, o r t ) * ( q 6 , ' u )e Q - F a n d w e L . Dcrnonstrating cllosureunder intel$t:ction

bv a modification of Definition 7.1. lffim,finrnqffi"!,ffif,il,il i A puslrdown automaton M : (Q,I, l, d, qo)zt F) is said to be deterministic if it is a-nautomaton as defineldirr Definition 7.1, subject to the restrictions ttrat, for every g E Q,e E X U {I} and b € f, 1. d (g, a, b) conttrins at rnost one eleinent, tust be empty for evcry c € E. The lirst of these conditions simplv requires that for any givcn input symbol and any stack top, at most one mov{} carr be made. The second condition

easily write a computer progralrr frrr it, and we rrray expect thtrt it will work t:fliciently. Sittce there may be .\-transitions involved, we cannot immediatcly claim that this will yield a linear-time parser, but it J.rutsus on lhe right track nevertheless. To purrrue this, let us see what grarnmars might be srritable for the description of deterministic contextfrec languages, Herc we enter a topic important irr the study of contpilers, but sorrrtlwhat peripheral to our interests. We will

matehing consecutive uymboftl, we would likc to know exactly which produr:tion rule is to be applied at each step. This would avoid backtracking and give us an efficient parser. The question then is wltether there are grilmmars that allow us to do this. For a general r:ontext-free grammar, this is not the case, but if the form of the grammar is restricted, we can achieve our goal. As first casc, ta,ke the s-grammars introdtrtnd in Definition 5.4. From the discussion thcre, it is clear that at