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

Faculty of Computational Mathematics and Cybernetics

Educational and methodological development for independent work of students in the course “Theory of Algorithms and Mathematical Logic”

while studying the topic “Concepts of finite state machine and 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 finite state machines and regular languages. Operations on regular languages”, which is part of the training course “Theory of Algorithms and Mathematical Logic”. The concept of a formal language and operations on formal languages, including basic set-theoretic operations, are introduced. The concept of a finite automaton is presented (in deterministic and non-deterministic versions); regular languages ​​are a class of languages ​​recognized by finite state machines. It is shown that operations, unions, intersections, additions, concatenations and iterations do not leave the class of regular languages. The corresponding algorithms for the synthesis of finite state machines are presented.

Compiled by:

teachers of the Department of Informatics and Automation of Scientific Research, Faculty of Computational Mathematics and Computer Science, 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; characters of an arbitrary alphabet are called letters. As examples, we will indicate the Russian alphabet (with or without the inclusion of punctuation marks), the Latin alphabet, a combination of these alphabets, and many digits of the decimal or binary number systems. In general, we define the alphabet as a set A = (a 1, a 2, ..., a n); among the letters of the alphabet A there may also be a special space character (empty letter); this character is usually denoted e (abbreviation of the English “empty” - empty).

A word in the alphabet A is an arbitrary finite sequence of its letters; the same letter can appear multiple times in this sequence. 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 (empty word); one should distinguish between an empty word and a 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 *. Let us specially note that the collection 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 *. We call a language L finite if it contains a finite set of words; a language L is infinite if it contains an infinite number of words. The totality of all words in Russian and all words in English are examples of finite languages. Lots of records of everyone prime numbers in the decimal or binary number system is an infinite language. The set of all languages ​​of the alphabet A has continuum cardinality.

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

we call it 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 will

denote the union and intersection of these languages, respectively. The word α belongs to a union of two languages ​​if it belongs to at least one of them; the word α belongs to the intersection of two languages ​​if it belongs to both one and the other language. Let L be a language in alphabet A; Let L c denote the complement of this language. The language L c is formed by words of the alphabet A that 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. We will denote by L 1 \L 2

difference between languages ​​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. It is obvious that the difference operation can be represented through the basic theoretical

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

Additionally, 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: the word α belongs to the language L 1 ( L 2 if and only if this word can be divided into two consecutive parts

(i.e., presented in the form α = α 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 concatenation (linking) of languages. The sign ( will often be omitted, then the concatenation of languages ​​L 1 and L 2 is written L 1 L 2. The language L 1 L 2 is obtained by adding words of language L 2 to words of language L 1 as endings. Note , that if an empty word is added to an arbitrary word γ, then the result will be the word γ. If the languages ​​L 1 and L 2 are finite, and the first language contains m words, and the second language contains n words, 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.

Let us 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 degree L i of 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 number of successive parts (subwords) so that each part belongs to the language L. If a language L consists of all single-letter words of the alphabet A, then an iteration of this language is the universal language A*. Note that for any language L we have (L *)*=L *.

In many languages, the following unary operator ()+ 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 finite state machine and regular language.

In cybernetics, automata are 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 state machines are studied as abstract algorithmic devices designed to process words of a fixed input alphabet. We assume that the automaton begins processing an arbitrary word α in the input alphabet A from a specially selected initial state. At each discrete time clock, the next letter of the word being processed arrives at the input of the machine; under its influence, the machine changes its state; The state into which the machine will go is determined by its previous state and the read letter of the input word. The machine works on a word of length l cycles. The result of the machine's operation is determined by the state in which it finds itself upon completion.

Formally, the finite automaton K is defined as a set

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

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

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

the state in which the automaton K finds itself after t cycles of work 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 α (р) F.

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

It is convenient to define a finite state machine by its transition diagram. The diagram is a directed graph, the vertices of which are identical to 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,a 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 a certain subset S, S A, all letters of this subset are signed above the corresponding arc (instead of a list of all letters, the abbreviated entry “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 with a bold circle highlighting the vertex q i.

Obviously, any finite state machine is completely defined 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.

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

q0 q1

Let's give a few more examples of regular languages ​​in the same alphabet: L 2 - a set of words in which the letter a occurs an even number of times; L 3 - a set of words starting and ending with the same letter; L 4

A 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 letters a and b encountered never exceeds 2. Diagrams of finite state machines K 2 - K 5 that recognize languages ​​L 2 - L 5, respectively, are presented in Figures 2.2 - 2.5. The machine “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 read, the number of letters a encountered exceeds the number of letters b encountered by x; here x (-2, -1, 0, 1, 2); the automaton is in state q bad if at some point in the operation of the automaton the absolute value of the difference between the number of processed letters a and the number of processed letters b exceeds 2.

We call the state of a finite automaton absorbing if any input letter does not take the automaton out of this state. Let's call the absorbing state positively absorbing, if it belongs to F, and negatively absorbing otherwise. In the 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 no more than one positively absorbing and no more than one negatively absorbing state (if there are several positively or negatively absorbing states, then they can easily be replaced by one). Typically, the negatively absorbing state is not depicted in a transition diagram; if a transition from a certain state by a certain letter is not indicated, then it is assumed that it leads to a negatively absorbing state. The finite machine 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 goes into it from state q 1 according to the letter c) is not indicated in the diagram.

q0 q1

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

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

Z A 79 Theory machine guns: guidelines for practical training for specialty 230101 / T.Z. Aralbaev,<...>The guidelines address the following issues: methods of presentation logical functions ( LF); algebraic transformation LF; minimization methods Quine and McClassky, using maps Carnot; forms assignments final machine guns; synthesis combinational schemes in the basis “ AND-NOT” (“OR-NOT"") on logical elements series K155 and K561.<...>Methodical instructions are intended for organizing practical classes on the course “ Theory machine guns” for 2nd year students in specialty 230101 “Computers, complexes, systems and networks.”<...>Minimizing logical functions across 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 Fundamentals digital machine guns”. <...>1.1 Tabular form of LF representation The logical function is most clearly represented by tables truth(TI) and cards Carnot. <...> Table truth- This table, in which each binary set of argument values ​​xi (i = 1, n) is associated with the value of the function Y = f (x1, x2,..., xi,..., xn) on this set. <...>A Carnaugh map is a rectangular table containing n 2 cells, with each cell located at the intersection of the i -th row and j -th column, ai and aj are the constituent elements binary recruitment n – local LF.<...>1) any pair of cells that are adjacent vertically or horizontally, as well as any pair of cells located symmetrically on the map vertically or horizontally, correspond binary sets, differing in the value of only one variable (i.e. differs in one digit);<...>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) BBK 32.97ya73 A 79 Reviewer: Doctor of Technical Sciences, Professor A.M. Pishukhin Aralbaev, T.Z A 79 Theory of automata: guidelines for practical training for specialty 230101 / T.Z. Aralbaev, I.V. Zhukalina. - Orenburg: State Educational Institution OSU, 2009. – 41 p. The guidelines address the following issues: methods of representing logical functions (LF); algebraic transformation of LF; Quine and McClassky minimization methods using Karnaugh maps; forms for specifying finite state machines; synthesis of combinational circuits based on “AND-NOT” (“OR-NOT”) on logic elements of the K155 and K561 series. The guidelines are intended for organizing practical classes in the course “Theory of Automata” for 2nd year students in specialty 230101 “Computers, complexes, systems and networks”. BBK 32.97ya73 © Aralbaev T.Z., 2009 © Zhukalina I.V., 2009 © State Educational Institution OSU, 2009 2

Page 2

Contents Introduction................................................... ........................................................ ...................4 1 Practical lesson No. 1. Methods of presenting logical functions……………………………….… 5 1.1 Tabular form of presentation of LF…………………………………….5 1.2 Analytical form of presentation of LF……… …………………………….8 2 Practical lesson No. 2. Algebraic transformation of formulas of logical functions………….…..12 2.1 Laws of Boolean algebra………………………………………………………12 2.2 Axioms and theorems of Boolean algebra………… ……………………………..12 3 Practical lesson No. 3. Quine and McClassky minimization method………….……………………….15 3.1 Finding all prime implicants……………………………………..15 3.2 Construction of the coverage table Quine matrices……………………………16 3.3 Finding the minimum covering of a function…………………………………….16 3.4 Obtaining the minimum form of the LF……… ………………16 4 Practical lesson No. 4. Minimization of logical functions using 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 5 Practical lesson No. 5 Forms of specifying finite state machines……… …………………………….……..25 6 Practical lesson No. 6 Synthesis of combinational circuits based on “AND-NOT” (“OR-NOT”)……….………30 7 Practical lesson No. 7. Synthesis of combinational circuits based on logic elements of the K155 and K561 series………………………………………………………………………………………….……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” - “Logical Foundations of Digital Automata”. The purpose of the classes is to practically consolidate knowledge about the forms of representation and methods for converting logical functions, as well as the methodology for synthesizing combinational circuits. Each practical lesson includes a statement of the purpose of the lesson, brief theoretical material on the topic, typical examples, test questions and exercises for independent work. Before conducting a lesson, the student must understand its purpose and answer control questions. For independent preparation for classes, students are recommended to read the literature presented in the list of sources used. During the lesson, examples are analyzed and exercises are performed based on options. Knowledge control is carried out based on the results of answering test questions and completing exercises. 4

Page 4

1 Practical lesson No. 1. Forms of representation of logical functions There are several forms of representation of logical functions (LFs) used at various stages of designing combinational circuits, in particular: verbal, tabular, analytical, geometric, cubic. The purpose of the practical lesson is to study tabular and analytical forms of LF representation and algorithms for the transition from a tabular description of LF to an analytical description. 1.1 Tabular form of LF representation The logical function is most clearly represented by means of a truth table (TI) and a Karnaugh map. A truth table is a table in which each binary set of argument values ​​xi (i = 1, n) is associated with 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 placed in the corresponding position of the TI. Table 1.1 – Truth table of the logical function N Х1 Х2 Х3 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 representing TI is used, which provides a list of sets of ones and zeros. Thus, the function considered in the example in list form can be represented as: Y = F Х Х Х) = ∨ (0, 1, 3, 6, 7) Y = ∧ (2, 4, 5) (0 1, 2 , 3 1 5

Excellent short lecture notes on the subject "automata theory" in Pdf file.

Synthesis of digital automata for implementation of binary arithmetic algorithms

• General information about digital machines. Glushkov's model. Synthesis of operating machines
• An example of synthesizing an operational automaton to perform 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 hard logic (UAL) for an algorithm for multiplying unsigned numbers in direct code

• Describe the model of a discrete Glushkov converter.
• What is the purpose of an Operational Automaton (OA)?
• List the stages of synthesis of an OA of a procedural type of canonical structure.
• Conduct OA synthesis 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 options (schemes) for indirect multiplication.
• Construct the timing diagram of OA for multiplication. Explain it.
• Synthesize an algorithm for performing an arithmetic operation by variants.
• Synthesize the OA circuit according to your algorithm.
• What is the purpose of the Control Automatic (CA)?
• The role of information and control signals.
• Types of UA.
• List the stages of synthesis of UA with rigid logic.
• Describe basic flip-flops as elementary state machines.
• What are the features of the synthesis of UAZL on different types triggers?
• Give structural diagrams of Mealy and Moore automata. What are their differences?
• Describe the models of abstract Mealy and Moore automata.
• What forms of description of abstract finite state machines do you know?
• Construct transition/output tables and automata graphs according to the scheme
• algorithm.
• Synthesize the UA to implement the multiplication algorithm (use
• simplified algorithm for indirect multiplication of unsigned numbers) as
• Mili/Moore automatic.
• Construct a timing diagram of the OA for multiplication. Explain it.
• Synthesize the UASL scheme for your algorithm according to the options.

Using regular expressions (RE). Software implementation of automata

• The concept of regular expressions and automata recognizers
• A quick introduction to regular expressions (RE). Dialects of RV.
• Application of RT in programming
• An example of forming a regular expression
• Example of working with regular expression to control user-entered IP addresses.
• Synthesis of a deterministic automaton for language recognition specified by a regular expression and its software implementation.
• Conversion of RF into NKA with ε – transitions
• Conversion of NKA with ε-transitions into NKA without ε-transitions
• Obtaining DKA from NKA without ε-transitions
• DFA minimization
• Receiving RF from spacecraft
• Software implementation of DFA recognizer

• What is a regular expression?
• Where are RVs used?
• What methods do you know for assigning RV?
• What automata are used to recognize the languages ​​specified by the RT?
• What is NKA? DKA?
• How to build a spacecraft recognizer using RV?
• How to build a DKA recognizer using RV?
• How to eliminate e-transitions in spacecraft?
• How to minimize the CA - recognizer?
• How are RTs used in the VS environment?
• How are RTs supported in the .NET Framework?
• Describe the given chains using RT.
• What chains does this RF define (examples, characteristics).
• Strategies for implementing RT support in software systems.
• Ways to use RT support when writing text processing programs.
• What text processing problems can be solved using RT?
• List the ones you know software systems, supporting RV.

Initial information about abstract automata of Mealy and Moore is given. Are given possible ways representations of automata: set-theoretic, graph, tabular and matrix, concepts of response of an automaton and equivalent automata. Methods for mutual equivalent transformation of automata are given. Are given general information about microprogram control, the concepts of microinstructions, microoperations, microprograms, methods of representing microprograms in the form of graph diagrams of algorithms (GDA), translation formulas, matrix and logical diagrams of algorithms. Methods for marking GSA and rules for constructing Mealy and Moore automata using them are given. The concept of a combined automaton and ways of representing it are given. Methods for the canonical synthesis of structural automata are considered. Examples of memory synthesis of a structural automaton based on RS-, T- and D-flip-flops are given.

Basic concepts and definitions.
The simplest information converter (Fig. 1.1, a) displays a certain set of information elements X arriving at the input into a certain set at the output Y. If the sets X and Y are finite and discrete, that is, the transformation is carried out at discrete moments in time, then such converters information are called final transformers. In this case, the elements of the sets X and Y are pre-encoded with binary codes and a transformation of one set to another is constructed.

The result of the transformation F: X → Y often depends not only on what information is in at the moment appeared at the input, but also from what happened before, that is, from the prehistory of the transformation. For example, the same input - a neighbor's apology after he stepped on your foot on a crowded bus - will cause you to have one reaction the first time and a completely different one the fifth time.

Content
Cover page Imprint
Lecture 1. Basic concepts of the theory of abstract automata
Lecture 2. Equivalent automata
Lecture 3. Methods of describing the operation of discrete devices
Lecture 4. Construction of abstract automata using a microprogram graph diagram
Lecture 5. Synthesis of a structural automaton
Lecture 6. Memory of a structural automaton
Lecture 7. An example of synthesis of a structural automaton using flip-flops
Lecture 8. Graphical method synthesis of a structural automaton on triggers.

Free download e-book in a convenient format, watch and read:
Download the book Introduction to the theory of automata, Knyazkov V.S., Volchenskaya T.V., 2016 - fileskachat.com, fast and free download.

Download pdf
You can buy this book below best price at a discount with delivery throughout Russia.