An Introduction to Formal Language and Automata Third Edition

This book is designed for an introductory course orr forrnir,l larrguages,
autornatir, txlmputability, and rclated matters. These topics form
a major part of whnt is known as tht: theory of cornputation. A
course on this strbitx:t rnatter is now stir,nda,rd in the comprrter sci-
ence curriculurn ancl is oftrlrr ta,ught fairly early irr the prograrn. Hence,
the Jrrospective audience for this book consists prirnrr,rily of sophomores and
juniors rnirjrlring in computer scicntxl or computer errgirrwring.
Prerequisites for the material in this book are a knowledge of sorne
higher-level prograrnrning la,nguage (cornmonly C, C++, or .Iava) and fa-
trrilinritv with ihe furrdarn<lnta,ls of data structures and algoriihms. A colrr$e
in discretc mathematics that irx:hrcles set theory, furrctions, relations, logic,
and elernerrts of mathematical reasorring is essential. Such a corlrse is part
of the standard introductory computer science curriculum.
The study of the theory of cornputa.tion has several purposc$, most im-
prortantly (1) to fa,miliarize studerrts with the fbundations and principles of
computer sciettce, (2) to teach tnaterial that is useful in subsequerrt colrrres!
rrnd (3) to strengtlrcrr utudents' ability tu t:ilrry out formal and rigorous
rrrirthematical argurnerrts.