Brief lectures on automata theory. Theory of automata Synthesis of digital automata for the implementation of binary arithmetic algorithms

A.A. Ozhiganov Theory of automata. Textbook - St. Petersburg: NRU ITMO, 2013. - 84 p. - copy.

Annotation:

The purpose of this study guide is to familiarize students with the methods of synthesis digital machines. Information about abstract Mealy and Moore automata is given. The paper considers tabular and graph representations of automata, introduces the notion of an automaton's response to an input word, and defines equivalent automata. Methods of mutual equivalent transformation of automata are presented. Are given general information about microprogram control, the concepts of microinstructions, microoperations, microprograms, ways of representing microprograms in the form of graph diagrams of algorithms (GSA), transition formulas, matrix and logic circuits algorithms. The GSA marking methods and the rules for constructing Mealy and Moore automata based on them are given. Methods of canonical synthesis of structural automata are considered. Examples of structural automaton memory synthesis based on D -, T -, RS - and JK flip-flops are given.

Description:

The manual is intended for students specializing in the field information technologies and can be used in the preparation of bachelors and masters in the areas of 230100 "Informatics and Computer Engineering”, 231000 “Software Engineering” and engineers in the specialty 230101 “Computers, complexes, systems and networks”.

Z A 79 Theory machine guns: guidelines for practical exercises for the specialty 230101 / T.Z. Aralbaev,<...>The guidelines address the following issues: ways of presenting logical functions ( LF); algebraic transformation LF; minimization methods Quina and McCluskey, with the help of maps Carnot; forms tasks final machine guns; synthesis combinational schemes in basis " AND-NOT” (“OR NO") on logical elements K155 and K561 series.<...>Methodical instructions are intended for the organization of practical classes on the course “ Theory machine guns” for 2nd year students in the specialty 230101 “Computers, complexes, systems and networks”.<...>Minimization of Boolean Functions by Maps Carnot ……………………….. <...>41 3 Introduction These guidelines contain material for conducting practical classes in one of the main sections of the discipline “Theory machine guns” – “Logical foundations digital machine guns”. <...>1.1 Tabular form of presentation of LF The logical function is most clearly represented by means of tables truth(TI) and cards Carnot. <...> Table truth- This table, in which each binary set of values ​​of the arguments xi (i = 1, n) is associated with the value of the function Y = f (x1, x2,..., xi ,..., xn) on this set.<...>Carnot's map is a rectangular table containing n 2 cells, each cell is located at the intersection of the i -th row and the jth column, ai and aj are constituent elements binary set n - local LF.<...>1) any pair of cells that are vertically or horizontally adjacent, as well as any pair of cells located symmetrically to the map vertically or horizontally, correspond to binary sets, differing in the value of only one variable (i.e. differs in one bit);<...>2) in cells cards Carnot indicates the values ​​of the function on the corresponding set;<...>3) binary sets of arguments that mark rows, as well as binary sets of arguments that mark columns<...>

Theory_automata.pdf

UDC 004.3(076.5) LBC 32.97ya73 A 79 Reviewer: Doctor of Technical Sciences, Professor A.M. Pishukhin Aralbaev, T.Z. A 79 Theory of automata: guidelines for practical exercises for the specialty 230101 / T.Z. Aralbaev, I.V. Zhukalina. - Orenburg: GOU OGU, 2009. - 41 p. The following issues are considered in the guidelines: methods of representing logical functions (LF); algebraic transformation of LF; Quine and McClussky's minimization methods using Karnot maps; forms of specifying finite automata; synthesis of combinational circuits in the basis of “AND-NOT” (“OR-NOT”) on logic elements of the K155 and K561 series. Methodical instructions are intended for organizing practical classes on the course “Automata Theory” for 2nd year students in the specialty 230101 “Computers, complexes, systems and networks”. BBC 32.97-73 © Aralbaev T.Z., 2009 © Zhukalina I.V., 2009 © GOU OGU, 2009 2

Page 2

Contents Introduction.................................................................. ................................................. ....................4 1 Practice #1. Ways of presenting logical functions………………………………….… 5 1.1 Tabular form of presentation of LF …………………………………………….5 1.2 Analytical form presentation of LF …………………………………….8 2 Practical lesson №2. Algebraic transformations of the formulas of logical functions………….…..12 2.1 Laws of Boolean algebra……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………. ……………………………..12 3 Practical lesson №3. Quine and McClussky's minimization method………….……………………….15 3.1 Finding all prime implicants…………………………………………..15 3.2 Building a table of coverages Quine matrices………………………………………………16 3.3 Finding the minimum coverage of a function………………………………………….16 3.4 Obtaining the minimum shape of the LF………………………… ………………16 4 Practical lesson №4. Minimization of logical functions by Karnaugh maps ………………………..20 4.1 Construction of minimal DNFs ……………………………………………...21 4.2 Construction of minimal CNFs ……… ……………………………………...22 4.3 Minimization of incompletely defined LFs………………………………..23 …………………………….……..25 6 Practical lesson No. 6 Synthesis of combinational circuits in the basis of “AND-NOT” (“OR-NOT”)……….………30 7 Practical lesson No. 7. The synthesis of combination circuits in the basis of the logical elements of the K155 and K561 ............................................................................................................................................. 35 List of sources used .... ................................................. ................40 Appendix…………………………………………………………………………...41 3

Page 3

Introduction These guidelines contain material for conducting practical classes in one of the main sections of the discipline "Theory of automata" - "The logical foundations of digital automata". The purpose of the classes is the practical consolidation of knowledge about the forms of representation and methods for transforming logical functions, as well as the methodology for synthesizing combinational circuits. Each practical lesson includes setting the goal of the lesson, a brief theoretical material on the topic, typical examples, Control questions and exercises for independent work. Before the lesson, the student must understand its purpose and answer control questions. For self-study students are recommended to study the literature presented in the list of used sources. During the lesson, examples are analyzed and exercises are performed according to the options. Knowledge control is carried out according to the results of answers to control questions and exercises. 4

Page 4

1 Practice #1. Forms of representation of logical functions There are several forms of representation of logical functions (LF) used at various stages of designing combinational circuits, in particular: verbal, tabular, analytical, geometric, cubic. The purpose of the practical lesson is to study the tabular and analytical forms of the LF representation and the algorithms for the transition from the tabular description of the LF to the analytical description. 1.1 Tabular form of representation of LF The logical function is most clearly represented by means of a truth table (TI) and a Karnaugh map. The truth table is a table in which each binary set of argument values ​​xi (i = 1, n) is assigned the value of the function Y = f (x1, x2,..., xi ,..., xn) on this set. Table 1.1 shows the TI function for three arguments as an example. The Y function takes the value 1 or 0 on each set. If the value of the function is not defined, then a dash is put in the corresponding position of the TI. Table 1.1 - Truth table of the logical function N X1 X2 X3 Y 0 0 0 0 1 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 1 7 1 1 1 1 Sometimes a list form of TI representation is used, which lists single and zero sets. So, the function considered in the example in list form can be represented as: Y = F X X X) = ∨ (0, 1, 3, 6, 7) Y = ∧ (2, 4, 5) (0 1, 2 , 3 1 5

An excellent short summary of lectures on the subject "automata theory" in Pdf-file.

Synthesis of digital automata for the implementation of binary arithmetic algorithms

• General information about digital machines. Glushkov model. Synthesis of operating automata
• An example of the synthesis of an operating automaton for performing indirect multiplication of unsigned numbers
• Types of control machines. Structures of Mealy and Moore automata.
• An example of the synthesis of a control automaton with rigid logic (SAR) for the algorithm for multiplying unsigned numbers in a direct code

• Describe the Glushkov discrete converter model.
• What is the purpose of the Operational Automaton (OA)?
• List the stages of synthesizing an OA of a procedural type of a canonical structure.
• Synthesize OA to perform multiplication (use simplified
• algorithm for indirect multiplication of unsigned numbers).
• Give an example of multiplying numbers using the indirect multiplication algorithm.
• Describe the main variants (schemes) of indirect multiplication.
• Plot the timing diagram of OA for multiplication. Explain it.
• Synthesize Execution Algorithm arithmetic operation by options.
• Synthesize the OA circuit according to your algorithm.
• What is the purpose of the Control Machine (UA)?
• The role of information and control signals.
• UA types.
• List the stages of synthesis of UA with rigid logic.
• Describe basic triggers as elementary state machines.
• What are the features of the synthesis of UAHL on different types triggers?
• Give block diagrams of Mealy and Moore automata. What are their differences?
• Describe models of abstract Mealy and Moore automata.
• What forms of description of abstract finite automata do you know?
• Build jump/output tables and automaton graphs according to the scheme
• algorithm.
• Perform VA synthesis to implement the multiplication algorithm (use
• simplified algorithm for indirect multiplication of unsigned numbers) as
• Mealy / Moore machine.
• Plot the VA timing diagram for the multiplication. Explain it.
• Synthesize the ALSL scheme for your algorithm by variants.

Using Regular Expressions (REs). Software implementation of automata

• The concept of regular expressions and automatic recognizers
• Brief information about regular expressions (RE). RV dialects.
• The use of real time in programming
• An example of the formation of a regular expression
• An example of working with regular expression to control user-entered IP addresses.
• Synthesis of a deterministic automaton for recognizing a language given by a regular expression and its software implementation.
• Transformation of RV into NCA with ε-transitions
• Transformation of an NFA with ε-transitions into an NFA without ε-transitions
• Obtaining DFA from NFA without ε-transitions
• DFA minimization
• Receipt of RV by KA
• Software implementation DFA-recognizer

Questions from the first section for self-control:

• What is a regular expression?
• Where are RVs used?
• What do you know how to set RW?
• With the help of what automata are the languages ​​given by RT recognized?
• What is NCA? DKA?
• How to build a KA-recognizer according to RV?
• How to build a DFA-recognizer according to RV?
• How to eliminate e-jumps in KA?
• How to minimize the CA - recognizer?
• How are RVs used in the VS environment?
• How are RVs supported in the .NET Framework?
• Describe the given chains using RE.
• What chains does this RT define (examples, characteristics).
• Strategies for implementing real-time support in software systems.
• Ways to use RT support when writing word processing programs.
• What tasks of word processing are solved with the help of RT?
• List the ones you know software systems that support RV.

Ministry of Education Russian Federation Nizhny Novgorod State University N.I. Lobachevsky

Faculty of Computational Mathematics and Cybernetics

Educational and methodological development for independent work of students on the course "Theory of Algorithms and Mathematical Logic"

when studying the topic “Concepts of a finite automaton and a regular language. Operations on Regular Languages»

Nizhny Novgorod 2000

The methodological development is intended for independent work of students of the specialty "Applied Informatics" on the material of the topic "Concepts of a finite automaton and a regular language. Operations on Regular Languages”, which is part of the course “Theory of Algorithms and Mathematical Logic”. The concept of a formal language and actions on formal languages, including basic set-theoretic operations. The concept of a finite automaton is presented (in deterministic and non-deterministic versions); regular languages ​​are a class of languages ​​recognized by finite automata. It is shown that operations, unions, intersections, additions, concatenations and iterations do not lead out of the class of regular languages. The corresponding algorithms for the synthesis of finite automata are given.

Compiled by:

teachers of the Department of Informatics and Automation scientific research Faculty of the VMK UNN Associate Professor, Doctor of Technical Sciences Kogan D.I. and assistant Babkina T.S.

1. The concept of language, examples of languages, operations on languages.

An alphabet is an arbitrary non-empty finite set of symbols; symbols of an arbitrary alphabet are called its letters. As examples, we indicate the Russian alphabet (with or without punctuation marks), the Latin alphabet, the union of the indicated alphabets, the set of digits of the decimal or binary number systems. IN general view the alphabet is defined as a set A \u003d (a 1, a 2, ..., a n); among the letters of the alphabet A there may be special character space (empty letter), this character is usually denoted by e (abbreviation of the English "empty" - empty).

By a word in the alphabet A we mean an arbitrary finite sequence of its letters; the same letter in this sequence can occur more than once. The length of the word α (notation l (α )) is the number of letters in this word. The special symbol λ will denote the only word that has zero length (the empty word ); one should distinguish between an empty word and the word e, consisting of one empty letter; the length of the word e (space) is equal to one. In the alphabet A =(a 1 , a 2 , ..., a n ) you can write n l different words of length l , where l =0, 1, 2, ... . The set of all words of the alphabet A will be denoted by A *. We specially note that the set A* also includes the empty word. The cardinality of the set of all words of the alphabet A is countable.

If α and β are two arbitrary words in the alphabet A , then αβ is the result of assigning the word β to the word α on the right. For any words α and β we assume that

αλ= λα= α, αλβ= αβ.

A language in the alphabet A is an arbitrary subset of words L from A * . A language L is called finite if it contains a finite set of words; A language L is infinite if it contains an infinite set of words. Sets of all Russian words, all words in English are examples of finite languages. The set of entries for all prime numbers in decimal or binary is an infinite language. The set of all languages ​​of the alphabet A has continual cardinality.

A language L in the alphabet A is called universal if L=A *. L language

we call empty if the set L is empty (L =).

Let L 1 and L 2 be languages ​​in the alphabet A . Through L 1 L 2 and L 1 ∩ L 2 we get

denote the union and intersection of these languages, respectively. A word α belongs to the union of two languages ​​if it belongs to at least one of them; a word α belongs to the intersection of two languages ​​if it belongs to both one and the other language. Let L be a language in the alphabet A; we denote by L c the complement of this language. The language L c is formed by words of the alphabet A , which are not part of the language L : L c = A *\L . The operations of union, intersection and addition are the main set-theoretic operations.

Let L 1 and L 2 be languages ​​in the alphabet A . Let L 1 \L 2 denote

language difference L 1 and L 2 . A word α from A * is considered to belong to L 1 \L 2 if and only if it belongs to the language L 1 but does not belong to the language L 2 . Obviously, the difference operation can be represented in terms of the main theoretical

multiple operations: L 1 \L 2 =L 1 ∩ (L 2 )c .

In addition, we introduce several special operations on languages. Let L 1 and L 2 be languages ​​in the alphabet A . Let L 1 ( L 2 denote the language

defined as follows: a word α belongs to the language L 1 ( L 2 if and only if this word can be divided into two consecutive parts

(i.e. represent as α = α 1 α 2 ) so that the first part is a word of the language L 1 , and the second part is a word of the language L 2 . The operation ( is called the concatenation (coupling) of languages. The sign ( will often be omitted, then the concatenation of the languages ​​L 1 and L 2 is written L 1 L 2. The language L 1 L 2 is obtained by attributing words of the language L 1 to the words of the language L 2 as endings. Note that if an empty word is attached to an arbitrary word γ as an ending, then the result will be the word γ... If the languages ​​L 1 and L 2 are finite, and there are m words in the first language, and n words in the second, then the language L 1 L 2 consists of at most mn words If one of the languages ​​L 1 , L 2 is empty, then L 1 L 2 is also an empty language.

We introduce the operation of raising a language to a power. We believe:

L 0 =(λ );

L1=L;

L2=LL; Ln +1 = Ln L, n=2, 3, ...;

thus, the concept of the degree L i of the language L is defined for any i =0, 1, 2, 3,

L* = U Li .

i=0

The introduced operation is called iteration. Note that the empty word belongs to an iteration of any language. A non-empty word α belongs to an iteration of the language L if and only if this word can be divided into a certain number of successive parts (subwords) so that each part belongs to the language L . If the language L consists of all one-letter words of the alphabet A, then the iteration of this language is the universal language A*. Note that for any language L we have (L *)*=L *.

In many languages, the following one-place operation ()+ is sometimes considered:

(L )+ =U L i .

i=1

The languages ​​L* and L+ differ from each other only in an empty word. The word λ always belongs to the language L*. It belongs to the language L + if and only if it belongs to the language L .

2. Concepts of a finite automaton and a regular language.

In cybernetics, automata are called technically or software-implemented modules designed to process incoming information. state machine is a module that has a finite number of possible states and operates in discrete time. In this tutorial, finite automata are studied as abstract algorithmic devices designed to process words of a fixed input alphabet. We assume that the automaton starts processing an arbitrary word α in the input alphabet A from a specially selected initial state. In each cycle of discrete time, the next letter of the processed word arrives at the input of the automaton, under its influence the automaton changes its state; the state into which the automaton will pass is determined by its previous state and the read letter of the input word. The automaton works on a word of length l for l cycles. The result of the operation of the automaton is determined by the state in which it finds itself after its completion.

Formally, the finite automaton K is defined as the set

K=( Q, A, q0 , g, F),

where Q =(q 0 , q 1 , q 2 , ..., q m ) is the set of automaton states; А =(а 1 , а 2 , ..., а n ) – input alphabet; q 0 is a specially selected state of the automaton, called the initial state; g is the state machine transition function,

which is a mapping of the type Q xA → Q (if g (q i ,а j )=q k , then the automaton from the state q i under the influence of the letter a j must go to the state q k ); F is a specially selected subset of automaton states, which we will conditionally call “good”, F Q .

the state in which the automaton K finds itself after t cycles of working on this word (here t = 0, 1, 2, ..., p ):

qα (0) =q0 ;

q α (1) = g (q α (0), a i 1 )

q α (2) = g (q α (1), a i 2 )

q α (p ) = g (q α (p − 1), a i p )

We will say that the word α is accepted by the automaton K if q α (p ) F .

Let us introduce the language L (К ): the word α belongs to the language L (К ) if this word is accepted by the automaton К . The language L (K ) is called the language recognized by the given finite automaton. A language L is called regular if it is possible to construct a recognizing finite automaton for it.

It is convenient to define a finite automaton by the diagram of its transitions. The diagram is a directed graph whose vertices are the same as the states of the automaton; an arc from vertex q i to vertex q k with the letter a j written above it is drawn if and only if g (q i ,а j )=q k . In the case when the transition from q i to q k is carried out under the influence of any of the letters of some subset S, S A, all letters of this subset are signed over the corresponding arc (instead of a list of all letters, the abbreviated notation "x S" or simply "S") is allowed. If an arbitrary state q i is included in F , then this fact is marked on the diagram by a bold circle highlighting the vertex q i .

Obviously, any finite automaton is completely determined by its transition diagram. Further, the task of constructing a finite automaton with certain properties will be understood as the task of constructing a diagram of its transitions.

On fig. 2.1 shows a diagram of the automaton K 1 working on the words of the alphabet A =(a,b,c). The automaton has two states, q 0 and q 1 , and only state q 1 is “good”. Having started work in the state q 0 , the automaton under the influence of the letters a, b does not leave this state; under the influence of the letter c, the transition to the state q 1 is realized; any further incoming letter leaves the automaton in the same state. Thus, the automaton K 1 recognizes the language L 1 , which consists of words containing the letter c . This language is regular.

q0 q1

Here are some more examples of regular languages ​​in the same alphabet: L 2 is the set of words in which the letter a occurs an even number of times; L 3 - set of words beginning and ending with the same letter; L 4

The set of words containing the subword α =abbc ; L 5 is a set of words, when reading from left to right, the difference between the number of encountered letters a and b never exceeds 2. Diagrams of finite automata K 2 - K 5 , recognizing languages ​​L 2 - L 5, respectively, are shown in Figures 2.2 - 2.5. The automaton “remembers” information about the processed part of the input word by its state. So, for example, the automaton K 5 , having processed some part of the input word, finds itself in the state q x , if in the part of the input word it has read, the number of met letters a exceeds the number of met letters b by x ; here x(-2, -1, 0, 1, 2); The automaton is in the state q bad if at some moment of the automaton's operation the absolute value of the difference between the number of processed letters a and the number of processed letters b exceeded 2.

		q bad

A state of a finite automaton is called absorbing if any input letter does not take the automaton out of this state. We will call the absorbing state positively absorbent if it belongs to F, and negatively absorbing V otherwise. In automata K 1 and K 4 the states q 1 and q 4 are positively absorbing, respectively, in the automaton K 5 the state q bad is negatively absorbing.

We can assume that each automaton has at most one positively absorbing and at most one negatively absorbing state (if there are several positively or negatively absorbing states, then they can easily be replaced by one). Usually, the negative absorbing state is not depicted in the transition diagram; if a transition from some state is not indicated by some letter, then it is assumed that it leads to a negatively absorbing state. The finite automaton shown in Figure 2.6 recognizes in the alphabet A a language consisting of words in which the letter c appears exactly once. This automaton has 3 states, the negatively absorbing state q is bad (the automaton passes into it from state q 1 by the letter c) is not indicated in the diagram.

q0 q1

Let us introduce the alphabet B =(0, 1, 2, …, 9), treat each word in this alphabet as a non-negative integer. Let L ( p ) denote the set of words - entries in the decimal number system of all integer non-negative numbers that are multiples of the natural constant p ; we assume that the language L (p )

additionally, the empty word λ also belongs. Let us show that L (p ) is a regular language. Recognizing L (p) finite automaton K (p) can be constructed as follows. We consider states of the automaton to be q 0 , q 1 , q 2 , q p –1 ; from an arbitrary state q i by the digit x, x (0, 1, 2, ..., 9), the machine switches to