Theory of Formal Languages, Automata, and Computation/Preface

Why study the theory of automata, languages, and computation (ALC)? It is not an area of high-profile research, and it’s not regarded as an applied area either, though some of the material is bread and butter, nuts and bolts computing – so pervasive that its invisible to many. That is, it’s a foundational course. Happily, I think, we study ALC because its engaging and fun for those interested in computation. In its abstractions you will find exercises in pure computational theory and computational thinking. Like a humanities class that you take as a computing student, if you are strongly inclined only towards the vocational thrusts of computing, and you still take a course on this material, I suggest that you take on faith that some-to-much of what you learn will come in handy later. I say “take on faith” because the links between theory and application probably won’t be as overt in this text as you would see in an algorithms text for example. There are, however, conceptual links between ALC and algorithms of course, programming languages, and artificial intelligence, which this book addresses.

I took “this class” in 1979 from a PhD student, Dov Harel, and I thought it was beautiful – I thought that the Pumping Lemma was a metaphor for life. The field hasn’t changed much (foundations don’t change much, or perhaps only rarely), though the onslaught of AI on the computational fields, and on other publics, has led to new analyses of how deep learning frameworks, which are dominant in AI and machine learning right now, fit into classical computational theory. While the book touches upon the recent work on AI, as well as classical material from AI, it is largely conventional in its treatment of the theory of formal languages, grammars, automata, and computation.

Maybe you’ll have a reaction to ALC something like mine (as well as other reactions perhaps) – it’s adoration of computing as a field that offers greater wisdom, not one that simply manifests as mastery of the latest gadgetry, but stems largely from an appreciation of computing’s earliest core abstractions.

The goal of the book is to "streamline" treatment of ALC to what I generally cover in a one semester course, with an organization that I prefer, with added treatments of applications too, including artificial intelligence (AI). My knowledge of this area resulted from undergraduate learning and from teaching undergraduates in the area, using primarily the texts of Hopcroft and Ullman, though I bring personal insights to the treatment, as well as treatment of the relationship of ALC to AI and machine learning. The exercises are often taken from other sources, and are cited as such. I add other exercises as well.

My original exercises uniquely include some that require students to interact with AIs to discuss material, and to vet these interactions. Instructors like me, who are not researchers in the area, but love it nonetheless, might recognize my interest in talking to AIs about this material -- who else would I be able to talk to about it in the normal course of my day!?! The interactions with large language models of AI are an opportunity for students to discuss ALC -- its methods, concepts, and philosophies -- in ways that they might never have done before. These AIs change the way that humans can now interact with computers, and they have the potential to rob us of something that is (or was) one of the unique skill sets of computer scientists -- the ability to communicate with the world's stupidest entity capable of response! I say "rob us" because the computers are seemingly less stupid by the day. Computer scientists are, or should be, among the world's best communicators in my opinion. The mode of communication, that is programming languages, are no longer necessarily needed, but at least in the foreseeable future some of the principles of good communication, such as the danger of making assumptions about what your conversation partner knows or believes, are still germane. The exercises on conversations with AIs on ALC material ask students to analyze, debug, expand, specialize, and otherwise interrogate their discussions.