Discussion—History of Finite Automata

Purpose

This exercise gives you insight into how the ideas of finite automata and regular languages developed, and reinforces your understanding of those ideas by helping you recognize the connections between the historical versions and their standard modern forms.

Background

Stephen Kleene invented much of what is now known about finite automata and regular languages. In this exercise you will read a discussion of, and substantial excerpts from, one of his papers on the subject.

This exercise is derived from the “Learning Discrete Mathematics and Computer Science Via Primary Historical Sources” project at New Mexico State University, Colorado State University Pueblo, and Old Dominion University. The specific document dealing with Kleene is due to Prof. Hing Leung of New Mexico State.

Activity

Read the “Regular Languages and Finite Automata” chapter available at http://www.cs.nmsu.edu/historical-projects/Projects/kleene.9.16.10.pdf. Then, using a discussion forum for this exercise on myCourses, develop a consensus on how (if at all) Kleene’s original definitions of finite automata and regular sets equate to the modern ones.

In particular, develop answers to the following questions:

• Is Kleene’s definition of “finite automaton” equivalent to the modern definition? If so, decide which modern definition (i.e., deterministic or nondeterministic) and sketch a proof of their equivalence. If not, develop one or more concrete examples of computations that one kind of automaton can do but the other can’t.
• Is Kleene’s definition of “event” really equivalent to the modern definition of “language”? If so, explain how; if not give concrete examples of things that are “events” in Kleene’s sense but not languages, or vice versa.
• If there is an equivalence between events and languages, is Kleene’s definition of “regular set” (i.e., regular language) equivalent to the modern definition? If so, sketch a proof of their equivalence. If not, give concrete examples of things that are regular sets under Kleene’s definition but not under the modern definition or vice versa.

I have already created the discussion forum for this exercise on myCourses. You can find it via the “Kleene’s Finite Automata Discussion” link on our “Course Materials” tab. This forum allows you to do the exercise collaboratively—no individual needs to completely answer every question by themselves. Indeed, I expect that each of you will offer a couple of ideas or partial solutions or questions, sometimes building on the things that others have offered, until all the questions are answered. In order to keep this process moving forward, please review the forum daily (or more often if you want), contributing where you can, until the “Complete By” date above.

I have already placed discussion threads in the forum for each question, and another one for general discussion. Please try to put your contributions to each question in that question’s thread. This will make it easier for others to find your ideas and see how they relate to other ideas.

I will monitor and participate in the discussion as I am able to. In particular, I will try to answer questions that arise or help threads that seem stuck.

Follow-Up

I will grade this exercise by reviewing the forum after the “Complete By” date. I will mainly base grades on the thoughtfulness and usefulness of your posts; this of course implies that I expect everyone to have some post(s) for me to look at.