Theory of automata. Theory of automata (80.00 rubles) Synthesis of digital automata for the implementation of binary arithmetic algorithms
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 forming 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
- 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 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 the inclusion of punctuation marks), the Latin alphabet, the union of the indicated alphabets, the set of digits of the decimal or binary number systems. AT 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 of English language 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 . It is obvious that 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 above 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. Let's call the absorbing state positively absorbent if it belongs to F, and negatively absorbing in 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
Initial information about abstract Mealy and Moore automata is given. are given possible ways representations of automata: set-theoretic, graph, tabular and matrix, concepts of automaton reaction and equivalent automata. Methods of mutual equivalent transformation of automata are given. Are given general information about microprogram control, the concepts of microinstructions, microoperations, microprograms, ways of representing microprograms in the form of graph-schemes of algorithms (GSA), translation formulas, matrix and logic circuits algorithms. The GSA marking methods and the rules for constructing Mealy and Moore automata based on them are given. The concept of a combined automaton and ways of its representation are given. Methods of canonical synthesis of structural automata are considered. Examples of structural automaton memory synthesis based on RS-, T- and D-flip-flops are given.
Basic concepts and definitions.
The simplest information converter (Fig. 1.1, a) maps a certain set of information elements X, incoming to the input, to a certain set of output Y. If the sets X and Y are finite and discrete, that is, the transformation is carried out at discrete times, then such converters information are called final converters. The elements of the sets X and Y in this case are pre-coded with binary codes and a transformation of one set into another is built.
The result of the transformation F: X → Y often depends not only on what information is in this moment appeared at the input, but also from what happened before, that is, from the prehistory of the transformation. For example, the same entrance - an apology from a neighbor after he stepped on your foot in a crowded bus - will cause you one reaction the first time and a completely different one the fifth time.
Content
Title page Imprint
Lecture 1. Basic concepts of the theory of abstract automata
Lecture 2. Equivalent automata
Lecture 3. Ways to describe the operation of discrete devices
Lecture 4
Lecture 5. Synthesis of a structural automaton
Lecture 6
Lecture 7
Lecture 8 Graphic 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.
The textbook contains extensive material on the theory of automata. It introduces the concept of an automaton, gives the theory of abstract and structural automata, and reveals questions about the theory of structural automata and homogeneous structures. The book covers with sufficient completeness the main results on the theory of finite automata, obtained by domestic and foreign authors during the emergence and development of the theory of automata.
Step 1. Choose books in the catalog and click the "Buy" button;
Step 2. Go to the "Basket" section;
Step 3. Specify the required quantity, fill in the data in the Recipient and Delivery blocks;
Step 4. Click the "Proceed to payment" button.
At the moment, it is possible to purchase printed books, electronic accesses or books as a gift to the library on the ELS website only with 100% advance payment. After payment, you will be given access to the full text of the textbook within Electronic Library or we start preparing an order for you at the printing house.
Attention! Please do not change the payment method for orders. If you have already chosen a payment method and failed to complete the payment, you need to re-register the order and pay for it in another convenient way.
You can pay for your order using one of the following methods:
- Cashless way:
- bank card: All form fields must be completed. Some banks ask you to confirm the payment - for this, an SMS code will be sent to your phone number.
- Online banking: banks cooperating with the payment service will offer their own form to fill out. Please enter the correct data in all fields.
For example, for " class="text-primary">Sberbank Online number required mobile phone and email. For " class="text-primary">Alpha Bank you will need a login in the Alfa-Click service and email. - Online wallet: if you have a Yandex wallet or Qiwi Wallet, you can pay for the order through them. To do this, select the appropriate payment method and fill in the proposed fields, then the system will redirect you to the page to confirm the invoice.
