- •1 Introduction (Введение)
- •2 Generalized block diagram of a finite state machine (Обобщенная структурная схема конечного автомата).
- •Push – вталкивать данные в стек;
- •Graphs (Графы)
- •Figure 3: Directed labeled graph for the edge detector Ориентированный помеченный граф для краевого детектора)
- •4 Finite State Machines (Конечные Автоматы)
- •5 Unified Modeling Language (Унифицированный язык моделирования)
- •Uml state machines (конечные автоматы унифицированного языка моделирования).
- •Fsm logic (логическая схема работы конечного автомата).
- •State diagrams versus flowcharts (диаграммы состояний в сравнении с блок-схемами программ)
- •Uml state diagram (диаграмма состояний уям)
- •Defining a State diagram (построение диаграммы состояний)
- •Elements of a State diagram (Элементы диаграммы состояний)
- •Asm Chart (диаграмма алгоритмического конечного автомата)
- •Detailed asm Chart (подробная диаграмма asm).
- •Register transfer level (Условное изображение на уровне rtl).
- •Rtl in the circuit design cycle (описание на уровне rtl для разработки имс).
- •Automata-based programming (программирование с помощью модели конечных автоматов).
- •Example (пример)
- •Traditional (imperative) program (обычная императивная программа).
- •Расшифровка операторов программы на языке с:
- •Automata-based style program (программа на основе модели конечного автомата)
- •A separate function for the automaton step (отдельная функция для этапа конечного автомата)
- •Explicit state transition table (таблица переходов состояний в явном виде)
- •Using object-oriented capabilities (использование объектно-ориентированных возможностей)
- •Other extensions
- •Moore machine
- •Formal definition
- •Mealy machine
- •Formal definition
- •Mathematical model
- •Advantages and disadvantages (преимущества и недостатки).
- •Formal definition (формальное определение).
- •Example (пример)
- •Example (пример)
- •Transformations from/to state diagram (переход от/к диаграмме состояний).
- •Directed graph of a finite state machine (направленный граф конечного автомата).
- •Harel statechart (диаграммы Harel).
- •С. State transition table (таблица смены состояний).
- •Δ and λ aren’t shown in Fig.1. Δ и λ не показаны на схеме для визуального упрощения.
- •The methods to define automata (Способы задания автоматов)
- •Transition and output tables (Таблицы переходов и выходов)
- •Transition and output tables for Mealy automaton (тпв автомата Мили)
- •Transition and output tables for Moore automaton (тпв автомата Мура)
Rtl in the circuit design cycle (описание на уровне rtl для разработки имс).
RTL is used in the logic design phase of the integrated circuit design cycle.
An RTL description is usually converted to a gate-level description of the circuit by a logic synthesis tool. The synthesis results are then used by placement and routing tools to create a physical layout.
Logic simulation tools may use a design's RTL description to verify its correctness.
Automata-based programming (программирование с помощью модели конечных автоматов).
Automata-based programming is a programming paradigm in which the program or its part is thought of as a model of a finite state machine or any other (often more complicated) formal automata (see automata theory). Sometimes a potentially-infinite set of possible states is introduced, and such a set can have a complicated structure, not just an enumeration.
Программирование с помощью модели конечных автоматов является таким принципом программирования, в котором или какого-либо другого (часто более сложного) формального автомата. Иногда вводится потенциально бесконечный набор состояний и такой набор может иметь усложненную структуру, а не просто перечисление.
программа или ее части рассматриваются как модель конечного автомата ии, система взглядов и понятий
FSM-based programming is generally the same, but, formally speaking, doesn't cover all possible variants as FSM stands for finite state machine and automata-based programming doesn't necessarily employ FSMs in the strict sense.
Программирование с помощью модели конечных автоматов в общем примерно такое же, но с формальной точки зрения не охватывает все варианты состояний моделей конечного автомата и это программирование не должно обязательно использовать модель конечных автоматов в точном смысле.
The following properties are key indicators for automata-based programming (следующие свойства являются ключевыми для программирование с помощью модели конечных автоматов):
The time period of the program's execution is clearly separated down to the steps of the automaton. Each of the steps is effectively an execution of a code section (same for all the steps), which has a single entry point. Such a section can be a function or other routine, or just a cycle body. The step section might be divided down to subsection to be executed depending on different states, although this is not necessary.
Период времени для выполнения программы четко подразделяется на этапы модели автомата. Каждый этап является эффективным в смысле выполнения команд секции программы (это относится ко всем этапам), которые имеют единую точку входа. Подобная секция может быть функцией или другой операцией (программой, стандартной программой), или просто телом цикла. Секция этапа программы может разделяться на подсекции, выполняемые в зависимости от различных состояний, хотя это и необязательно.
Any communication between the steps is only possible via the explicitly noted set of variables named the state. Between any two steps, the program (or its part created using the automata-based technique) can not have implicit components of its state, such as local (stack) variables' values, return addresses, the current instruction pointer etc. That is, the state of the whole program, taken at any two moments of entering the step of the automaton, can only differ in the values of the variables being considered as the state of the automaton.
The whole execution of the automata-based code is a (possibly explicit) cycle of the automaton's steps.
Любые виды связи между этапами возможны только через четко определенный набор переменных, называемых состояние. Между любыми двумя этапами программа (или ее части, созданные с помощью аппарата конечных автоматов) может не иметь свойственных компонентов этого состояния, таких как значения локальных (стековых) переменных, адресов возврата, указателя текущей команды и т.д. То есть состояние всей программы, взятое в любые 2 момента времени входа в этап конечного автомата, могут отличаться значениями переменных, которые рассматриваются как состояние конечного автомата.
Another reason to use the notion of automata-based programming is that the programmer's style of thinking about the program in this technique is very similar to the style of thinking used to solve maths-related tasks using Turing machine, Markov algorithm etc.
Другой причиной использования понятия программирования с помощью модели конечных автоматов является стиль осмысления программы с помощью этой техники, который подобен осмыслению решения математических задач с использованием концепции машины Turing, алгоритма Маркова и т.п.
A Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation and can represent any mathematical expression from its simple notation.