Another approach is to use dynamic programming that resembles Floyd-Warshall’s algorithm for computing transitive closure of a graph. The construction requires the introduction of the concept of generalized nondeterministic finite automata. Notes on Exercise 3.3: Some textbooks use the state elimination method in constructing a regular expression from a given finite automaton. So, the mechanism for determining the state of an inner cell can indeed be summarized by a sequential procedure (as employed in the addition logic).
Recall that, with Kleene’s model, the logic for determining the i-th bit (an inner cell) at time t is said to be “determined by the states of all the cells at time t – 1.” However, Kleene’s model leaves it wide open how the states of all the cells at time t − 1 decide the state of an inner cell at time t. Notes on Exercise 2.2: The usual logic for addition requires the carry bit to be passed sequentially from the lower ordered digits to the higher ordered digits as the addition process is performed. Given that the exercises are open-ended questions, it is advised that the instructor should carefully work through the project before assigning it to the students. Exercises 2.1-2.5 can be completed in one week, while the rest of the exercises are completed in the second week. Students can work on the project individually or in groups of two or three. Otherwise, the instructor can use some class time to go over materials in the project that the students find challenging. If the students are strong in mathematical thinking and proofs, an instructor may wish to assign the project as homework. The completion of the project requires two weeks. Also presented in the project is Kleene’s proof of the equivalence between the expressiveness of regular expressions and finite automata. Students will learn that Kleene’s original definition of a finite automaton is more liberal than the textbook’s definition given by Rabin and Scott. Before working on the project, students are expected to have studied the concepts of finite automata and regular languages from a modern textbook. The project can be used in a senior undergraduate or beginning graduate level course on the theory of computation. For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science. Our project is part of a larger collection published in Convergence. The comprehensive “Notes to the Instructor” presented next are also appended to the project itself. Our project, Regular Languages and Finite Automata, is ready for students, and the Latex source is also available for instructors who may wish to modify the project for students.
In particular, we learn Kleene’s own proof of the theorem, now called Kleene’s theorem, that shows finite automata and regular expressions are equivalent in their expressiveness for denoting languages. In this project for computer science students in a theory of computation course, we study Kleene’s concept of finite automata and regular expressions. While a lower level assembly-styled language with simpler syntax is sufficient to program the computer to do whatever a high level language can do, the programming community embraces higher level programming languages like Java, C++, and Python for higher productivity. A similar situation happens with programming languages. However, Kleene’s more complex model of finite automata actually allows the user to express ideas more easily, even though formally both models are equivalent in their expressiveness. In a paper published in 1959, Michael Rabin and Dana Scott presented finite automata in the simplest mathematical model. A finite automaton can be considered as the simplest machine model in that the machine has a finite memory that is, the memory size is independent of the input length. Following on their ideas, Stephen Cole Kleene (1909–1994) wrote the first paper on finite automata and regular expressions in 1956. In 1943, Warren McCulloch and Walter Pitts published a pioneering work on a logical model for studying the behavior of nervous systems in the Bulletin of Mathematical Biophysics. Stephen Cole Kleene (Source: Wikimedia Commons)
0 kommentar(er)
