Topic 8

Lesson 8. Abstract Automata

Objective: involves hierarchical mastery of skills, starting from understanding the basics of the abstract automaton model and ending with the ability to construct and evaluate the equivalence of different types of automata. At the lowest level, Knowledge/Remembering, the student must define the concepts of an abstract automaton  and a finite automaton, list the components that define a non-initial automaton (K, X, Y, ), and name the two main types of automata: recognizers and converters. The next level, Understanding, requires the student to explain the need for the emergence of automaton theory in connection with the creation of technical means of automatic control and computing systems, interpret the differences between Milley and Moore automata (where in Milley the output signal occurs simultaneously with the input signal, and in Moore - with a delay of 1 clock cycle), and formulate the concepts of deterministic and non-deterministic automata. The Applying level  assumes that the student will demonstrate the practical use of knowledge, in particular, will apply the transition function delta and the output function gamma to calculate the next state and output symbol of the automaton, use a tabular or graphical method to specify the finite automaton, and also solve the problem of determining the language recognized by the finite automaton. The fourth level, Analyzing, requires the student to compare the structure and operation of Mealy and Moore automata, distinguish the computational capabilities of different types of automata according to the complexity of the work stream (e.g., MT, LOA, MP automaton, CA), and analyze the conditions under which two finite automata are considered equivalent. At the fifth level, Evaluating, the student must justify the importance of the theorem on the closed set of regular languages ​​with respect to operations (iteration, product, union), criticize the limitations of the finite automaton (FA) compared to the Turing machine (TM) due to the lack of a work stream, and evaluate the equivalence of Mealy and Moore automata. At the highest level, Creating, the student must design an algorithm to minimize a finite state machine 15, as well as design a finite state machine graph that recognizes a given regular language.