- •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 (тпв автомата Мура)
A separate function for the automaton step (отдельная функция для этапа конечного автомата)
The most important property of the previous program is that the automaton step code section is clearly localized. It is possible to demonstrate this property even better if we provide a separate function for it:
Наиболее важным свойством предыдущей программы является то, что секция ее текста, относящаяся к этапу работы конечного автомата, четко локализована. Имеется возможность продемонстрировать это свойство, если мы выделим отдельную функцию для этого:
#include <stdio.h>
enum states { before, inside, after };
void step(enum states *state, int c)
{
if(c == '\n') {
putchar('\n');
*state = before;
} else
switch(*state) {
case before:
if(c != ' ') {
putchar(c);
*state = inside;
}
break;
case inside:
if(c == ' ') {
*state = after;
} else {
putchar(c);
}
break;
case after:
break;
}
}
int main()
{
int c;
enum states state = before;
while((c = getchar()) != EOF) {
step(&state, c);
}
return 0;
}
Расшифровка программы:
void step(enum states *state, int c) \\ - если функция вообще не объявлена, на месте списка типов указывается void;
step(&state, c); \\ - &state – оператор получения адреса;
This example clearly demonstrates the basic properties of automata-based code:
Этот пример прекрасно демонстрирует основные свойства текста программы, основанной на работе конечного автомата:
time periods of automaton step executions may not overlap (периоды времени этапа исполнения программы конечного автомата могут не иметь наложения (перекрытия);
the only information passed from the previous step to the next is the explicitly specified automaton state – единственная информация, перешедшая из предыдущего шага, является четко определенным состоянием конечного автомата.
Explicit state transition table (таблица переходов состояний в явном виде)
A finite automaton can be defined by an explicit state transition table. Generally speaking, an automata-based program code can naturally reflect this approach. In the program below there's an array named the_table, which defines the table. The rows of the table stand for three states, while columns reflect the input characters (first for spaces, second for the end of line character, and the last is for all the other characters).
Конечный автомат может быть определен с помощью таблицы переходов состояний в явном виде. Вообще говоря, программа, основанная на модели конечного автомата, может, естественно, отражать подобный подход. В нижеприведенной программе имеется матрица (массив), называемый the_table, который определяет таблицу. Ряды таблицы устанавливаются для 3-х состояний, в то время как колонки отображают входные символы (1-я для отступов, 2-я – для конца строки символов и 3-я – для всех остальных символов).
For every possible combination, the table contains the new state number and the flag, which determines whether the automaton must print the symbol. In a real life task, this could be more complicated; e.g., the table could contain pointers to functions to be called on every possible combination of conditions.
Для каждой возможной комбинации таблица содержит номер нового состояния и флаг (признака), который определяет, должен ли конечный автомат печатать символ. В реальном мире это должно быть усложнено, например, таблица может содержать указатели функций, вызываемых в случае каждой возможной комбинацией событий.
#include <stdio.h>
enum states { before = 0, inside = 1, after = 2 };
struct branch {
enum states new_state:2;
int should_putchar:1;
};
struct branch the_table[3][3] = {
/* ' ' '\n' others */
/* before */ { {before,0}, {before,1}, {inside,1} },
/* inside */ { {after, 0}, {before,1}, {inside,1} },
/* after */ { {after, 0}, {before,1}, {after, 0} }
};
void step(enum states *state, int c)
{
int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
struct branch *b = & the_table[*state][idx2];
*state = b->new_state;
if(b->should_putchar) putchar(c);
}
int main()
{
int c;
enum states state = before;
while((c = getchar()) != EOF)
step(&state, c);
return 0;
}
Расшифровка программы:
-> \\ - оператор доступа к элементу структуры через указатель;
struct \\ - объявление структуры;
* \\ - оператор косвенного доступа;