Pull to refresh

Comments 30

Как создать обычную процедурную модель (см. листинг 4) или как реализовать автомат в ВКПа (см. листинг 5) понятно, но как это же повторить на базе событийного автомата библиотеки Qt не очень ясно из-за проблемы реализации перехода из состояния «1» в состояние «0», требующего одновременного анализа нескольких событий.

Да всё совершенно понятно и очевидно. Вам просто нужны 4 состояния, а не два.


Но дело не только в числе состояний. На самом деле, вам просто не нужен автомат чтобы сделать И-НЕ. Смотрите как просто делается И-НЕ на Qt:


class Ine
{
public:
    bool x1, x2;

    bool output() {
        return !(x1 && x2);
    }
};
UFO just landed and posted this here

Ну, это уже зависит от выбранного API для связей. Да, можно и на сигналах-слотах сделать. А можно вообще отдельного класса для "И-НЕ" не создавать...

У меня не проблема сделать модель конкретно элемента И-НЕ. Это лишь пример, на котором проявляется проблема реализации автоматов в Qt, т.к. не ясно можно ли пометить переход несколькими событиями. В UML четко сказано — нельзя. Может нельзя и здесь, а, возможно, это лишь мое предположение. В MATLAB разрешили совсем не помечать переход событиями. Т.е. у меня проблема сделать автомат средствами автоматных классов Qt, аналогичный автомату на рис. 4. Я не знаю, как сделать переход, помеченный двумя событиями по типу конъюнкции (см. переход из 0 в 1, помеченный x1x2). В книге [1] показано, как использовать автоматные классы для реализации калькулятора, но в его модели нет таких переходов (см. рис.1 и рис.2). Я бы хотел сделать аналогичный код для автомата на рис. 4. Может, в доках по Qt есть что-то на эту тему?

Очевидно, что любые конъюнкции легко(но не всегда красиво) разделяются на отдельные события.
Как и дизъюнкции.
Это базовые понятия булевой алгебры, которые применяются в теории автоматов.

События — на то и события, что всегда приходят по-одному. У вас нет событий x1 и x2, у вас есть события "сигнал x1 появился", "сигнал x1 пропал", "сигнал x2 появился" и "сигнал x2 пропал".


Для реализации любой логической функции на событиях вам нужно 2N состояний, где N — число входов. Просто кодируйте каждую входную комбинацию отдельным состоянием и всё.

Можно еще СК(Д)НФ минимизировать.

В рамках используемой модели структурного автомата все уже минимизировано. Проще, чем на рис. 4, уже не будет.

Очевидно, что речь не о базисных функциях типа И-НЕ.
Кармы не хватает, потому напишу здесь относительно следующего комментария про одновременность.
Нет нужды в одновременности в ДКА, потому всё можно сделать по заветам Мили и Мура, просто выйдет много "дополнительных" состояний.
Зато будет работать, если формально верифицировать.
Можно заморочиться, конечно, и сделать генерацию внутренних промежуточных состояний — задача не очень сложная, на самом деле.

К чему все это, если уже есть готовый, правильный и минимизированный структурный автомат на рис.4. Его только надо реализовать и больше ни над чем не париться — дополнительными, промежуточными состояниями, событиями и т.д. и т.д. Я-то именно об этом и написал, т.к. то, что есть в Qt уж больно «коряво». Вот об чем речь.
События могут приходить и одновременно (см… мою цитату о событиях из [10]). Но мысль понятная. Попробую реализовать… Изврат, конечно, но… По-любому, думаю, без событий будет проще и, главное, правильнее с точки зрения той же теории.

Не вижу каким образом без событий может быть "правильнее" с точки зрения теории. Это просто разные входные данные. Конечный автомат может работать с любыми.

Перечитайте статью. Так все рассказано и как раз по этой теме — почему правильнее. Повторю. В теории автомат работает только с сигналами (см. ссылки на литературу по ТКА). Поэтому «любые» приводятся к сигналам. Как у меня, где есть функция-предикат, которая «любые» данные приводит к «булеву сигналу» или по-другому к двоичному сигналу.

Вообще-то в теории автомат работает с входным алфавитом. Который на практике может быть как сигналами, так и событиями.

Интересно вы Мили с Муром смешали.
Сразу видно опытного опровергателя теорий с практикой.

Ну, это не моя идея — «мешать» автоматы Мили и Мура. Тут Вы меня явно перехвалили ;) Чтобы так «мешать» опыта совсем не надо — достаточно начальных сведений из теории автоматов. В ней это обычная модель. Ее еще часто называют С-автоматом.
Т.к. я не привел в статье, то на всякий случай код автомата из [1]:
#ifndef CALCULATOR_H
#define CALCULATOR_H

#include <QObject>

class QStateMachine;
class QState;

enum Buttons {
    digit0 = 0,
    digit1,
    digit2,
    digit3,
    digit4,
    digit5,
    digit6,
    digit7,
    digit8,
    digit9,
    opPlus,
    opMinus,
    opCancel,
    opEqual,
    opNone
};

class QWidget;
class Calculator : public QObject
{
    Q_OBJECT
public:
    explicit Calculator(QObject *parent = nullptr);
signals:
    void valueChanged(int value);
    void digitButtonPressed();
    void operationButtonPressed();
    void cancelButtonPressed();
    void equalButtonPressed();
public slots:
    void digitButtonPressed(int button);
    void operationButtonPressed(int button);
private slots:
    void s1Entered();
    void s1Exited();
    void s2Entered();
    void s2Exited();
    void s3Entered();
    void s3Exited();
    void s4Entered();
    void s4Exited();
    void s5Entered();
    void s5Exited();
private:
    int Rf, Rb;
    Buttons transitionButton, Op;
    void doOp(Buttons op);
    QStateMachine * machine;
    QState * s1;
    QState * s2;
    QState * s3;
    QState * s4;
    QState * s5;

};

#endif // CALCULATOR_H
#include "calculator.h"
#include <QWidget>
#include <QStateMachine>
#include <QState>

Calculator::Calculator(QObject *parent) :
    QObject(parent)
{
    Rf= 0;
    Rb = 0;
    Op = opNone;
    emit valueChanged(Rf);
    s1 = new QState();
    s2 = new QState();
    s3 = new QState();
    s4 = new QState();
    s5 = new QState();
    s1->addTransition(this, SIGNAL(digitButtonPressed()), s2);
    s2->addTransition(this, SIGNAL(cancelButtonPressed()), s1);
    s2->addTransition(this, SIGNAL(digitButtonPressed()), s2);
    s2->addTransition(this, SIGNAL(operationButtonPressed()), s3);
    s3->addTransition(this, SIGNAL(cancelButtonPressed()), s1);
    s3->addTransition(this, SIGNAL(operationButtonPressed()), s3);
    s3->addTransition(this, SIGNAL(digitButtonPressed()), s4);
    s3->addTransition(this, SIGNAL(equalButtonPressed()), s5);
    s4->addTransition(this, SIGNAL(cancelButtonPressed()), s1);
    s4->addTransition(this, SIGNAL(digitButtonPressed()), s4);
    s4->addTransition(this, SIGNAL(operationButtonPressed()), s3);
    s4->addTransition(this, SIGNAL(equalButtonPressed()), s5);
    s5->addTransition(this, SIGNAL(cancelButtonPressed()), s1);
    s5->addTransition(this, SIGNAL(digitButtonPressed()), s2);
    s5->addTransition(this, SIGNAL(operationButtonPressed()), s3);
    connect (s1, SIGNAL(entered()), this, SLOT(s1Entered()));
    connect (s1, SIGNAL(exited()), this, SLOT(s1Exited()));
    connect (s2, SIGNAL(entered()), this, SLOT(s2Entered()));
    connect (s2, SIGNAL(exited()), this, SLOT(s2Exited()));
    connect (s3, SIGNAL(entered()), this, SLOT(s3Entered()));
    connect (s3, SIGNAL(exited()), this, SLOT(s3Exited()));
    connect (s4, SIGNAL(entered()), this, SLOT(s4Entered()));
    connect (s4, SIGNAL(exited()), this, SLOT(s4Exited()));
    connect (s5, SIGNAL(entered()), this, SLOT(s5Entered()));
    connect (s5, SIGNAL(exited()), this, SLOT(s5Exited()));
    machine = new QStateMachine(nullptr);
    machine->addState(s1);
    machine->addState(s2);
    machine->addState(s3);
    machine->addState(s4);
    machine->addState(s5);
    machine->setInitialState(s1);
    machine->start();
}

void Calculator::digitButtonPressed(int button)
{
    transitionButton = static_cast<Buttons>(button);
    emit digitButtonPressed();
}

void Calculator::operationButtonPressed(int button)
{
    transitionButton = static_cast<Buttons>(button);
    if (button == opCancel)
        emit cancelButtonPressed();
    else
        if (button == opEqual)
            emit equalButtonPressed();
        else
            emit operationButtonPressed();
}

void Calculator::s1Entered()
{
    Rf = 0;
    Rb = 0;
    Op =  opNone;
    emit valueChanged(Rf);
}

void Calculator::s1Exited()
{

}

void Calculator::s2Entered()
{
    if (Rf < 9999999) {
        Rf = Rf*10 + transitionButton;
        emit valueChanged(Rf);
    }
}

void Calculator::s2Exited()
{

}

void Calculator::s3Entered()
{
    if (Rb != 0) {
        doOp(Op);
        emit valueChanged(Rf);
    }
    Rb = Rf;
    Op = transitionButton;
}

void Calculator::s3Exited()
{
    if (transitionButton > 9) {
        doOp(Op);
        Rb = 0;
        Op = transitionButton;
        emit valueChanged(Rf);
    } else  {
        Rf = 0;
    }
}

void Calculator::s4Entered()
{
    s2Entered();
}

void Calculator::s4Exited()
{

}

void Calculator::s5Entered()
{
    doOp(Op);
    Op = opNone;
    emit valueChanged(Rf);
}

void Calculator::s5Exited()
{
    if (transitionButton <= 9) {
        Rb = 0;
        Rf = 0;
    }
}

void Calculator::doOp(Buttons op)
{
    switch (op) {
    case opPlus:
        Rf = Rf + Rb;
        break;
    case opMinus:
        Rf = Rb - Rf;
        break;
    default:
        break;
    }

}

Я бы порекомендовал гитхаб для таких простыней.

Может, Вы и правы. Подскажите как.
Вот «событийный автомат» средствами Qt. Не проверял, но, надеюсь, работать будет:
#ifndef EINE_H
#define EINE_H

#include <QObject>

class QStateMachine;
class QState;
class EIne : public QObject
{
    Q_OBJECT
public:
    explicit EIne(QObject *parent = nullptr);
    bool bX1, bX2, bY;
signals:
    void setX1X2();
    void setNotX1();
    void setNotX2();
private:
    QStateMachine * machine;
    QState *s0, *s1;
private slots:
    void y1() { bY = false; }
    void y2() { bY = true; }
};

#endif // EINE_H
#include "EIne.h"
#include <QWidget>
#include <QStateMachine>
#include <QState>

EIne::EIne(QObject *parent):
    QObject(parent)
{
    s0 = new QState();
    s1 = new QState();
    s1->addTransition(this, SIGNAL(setX1X2()), s0);
    s0->addTransition(this, SIGNAL(setNotX1()), s1);
    s0->addTransition(this, SIGNAL(setNotX2()), s1);
    connect (s0, SIGNAL(setX1X2()), this, SLOT(y1()));
    connect (s1, SIGNAL(setNotX1()), this, SLOT(y0()));
    connect (s1, SIGNAL(setNotX2()), this, SLOT(y0()));
    machine = new QStateMachine(nullptr);
    machine->addState(s0);
    machine->addState(s1);
    machine->setInitialState(s1);
    machine->start();
}

Еще должен быть код проверки состояния входов (bX1, bX2), который в зависимости от их состояния будет посылать сигналы.

Нее, вот такого события — setX1X2 — у вас в автомате точно быть не может. Просто подумайте кто его может послать и сколько усилий для этого придется затратить...

Ну, так в этом и есть «фишка» — создать одно (!) событие в процессе анализа нескольких (!) условий (входов). Пусть есть диалог, а на нем два переключателя для установки входов. Так вот в слоте для каждого переключателя проверяется состояние не только своего, но и другого. И если оба переключателя установлены, то и посылается сигнал setX1X2. А уж автомат, если находится в состоянии s1, на него и должен среагировать, перейдя в состояние s0.

Реализация этой "фишки" сложнее всего вашего автомата целиком.

Да нет. На самом деле все просто. Беспокоит, что, похоже, в подобной ситуации только так и нужно будет поступать. Может, правда, я не прав? Например, в UML переход помечается: событие[условие/действие]. Неужели в автоматах Qt только событие?

Автоматы придуманы чтобы описывать с их помощью логику, а вы эту логику оставили, видимо, среди интерфейса пользователя. Зачем вам вообще автомат с таким подходом? y1 = !(x1 && x2) можно и без автомата написать как бы.


Наиболее "сложная" операция тут — &&. Если вы решили делать её автоматом в учебных целях — то и делайте автоматом, а не выносите за его пределы.

Автоматы придуманы, как модель дискретного преобразователя (ДП) (см., например, Глушков В.М. Введение в кибернетику), который преобразует строки из входного алфавита в строки выходного алфавита. Входным сигналом сигналом является буква входного алфавита и т.д. и т.д. Автомат, безусловно, реализует некую логику. Но, прежде всего, он — модель управления для некой алгоритмической машины. То, о чем Вы говорите — действие (y1=...). Чисто действие без управления — ноль (см. мою предыдущую статью). Всегда есть действия и управление. Вместе они реализуют некий алгоритм.
Автоматы нужны, чтобы сформировать более совершенную парадигму/технологию программирования. Модель И-НЕ — пример в рамках подобной парадигмы. В форме на рис. 4 — это лишь пример простого процесса. Пример алгоритма, отражающего свойства предлагаемой парадигмы. И не более того.
Если бы я хотел минимизировать именно модель И-НЕ, то я мог бы привести и такой автомат, состоящий из одного состояния и петли, нагруженной действием y1 =… И он бы также, как и автомат на рис. 4, реализовал тот же процесс — алгоритм реализации работы элемента (это важно! процесс, а не просто логическая операция И-НЕ, как действие).
Просто модель на рис. 4 позволяет показать вещи, которые в принципе не возможны в блок-схемной модели. Например. Не нужна логическая операция &&, не нужна операция отрицания !, не нужна переменная y1, отражающая состояние выхода элемента (ее роль взяли на себя состояния автомата). Здесь другое управление — таблица переходов. Здесь параллелизм — анализ двух входов сразу. Здесь параллелизм работы управления — выбор перехода из состояния 0. Уф! — устал перечислять :) А есть, ведь, еще, еще и еще… Но об этом будут дальше статьи…
Короче. Современное программирование — каменный век. Нужно что-то делать. Автоматное программирование — одно из предложений, которое доказало свою работоспособность. Нужно только довести его до нормальной кондиции. Процесс этот идет…
Чисто действие без управления — ноль (см. мою предыдущую статью). Всегда есть действия и управление. Вместе они реализуют некий алгоритм.

Управление у вашей алгоритмической машины уже есть — это, внезапно, ваша программа. Когда у вас имеется в наличии программируемое устройство, вам уже не нужен конечный автомат безусловно. КА следует использовать только тогда, когда он что-то упрощает.


Если бы я хотел минимизировать именно модель И-НЕ, то я мог бы привести и такой автомат, состоящий из одного состояния и петли, нагруженной действием y1 =…

И это было бы правильным решением! Ну, за исключением того, что вырожденный КА можно без проблем убрать из кода.


Просто модель на рис. 4 позволяет показать вещи, которые в принципе не возможны в блок-схемной модели. Например. Не нужна логическая операция &&

Вот я вам и говорю: если вы пытаетесь показать что вам не нужна операция && — так напишите код без этой операции! Не надо вот этого: "в слоте для каждого переключателя проверяется состояние не только своего, но и другого. И если оба переключателя установлены, то и посылается сигнал setX1X2." — вы там внутри всё равно будете использовать операцию &&, т.е. задача реализовать && у вас оказалась невыполненой.


Здесь параллелизм — анализ двух входов сразу. Здесь параллелизм работы управления — выбор перехода из состояния 0.

Здесь нет никакого параллелизма. От того, что вы расположили эти "стрелочки" на своей диаграмме параллельно — интерпретатор КА параллельным не стал.


И это общее ограничение для любых КА — обработка символов входного алфавита всегда последовательная, это заложено в модель.


Короче. Современное программирование — каменный век. Нужно что-то делать. Автоматное программирование — одно из предложений, которое доказало свою работоспособность.

Вообще-то, всё строго наоборот. Это автоматное программирование — каменный век. Процесс отказа от которого всё ещё идет.

Управление в моей автоматной программе (см. листинг 5) — это таблица переходов (ТП) T_INE. Она заменяет управление обычной программы, которое, как правило, представлено управляющими операторами типа if, do, while, swich и т.д и т.д. Строго говоря, я работаю на «автоматном процессоре», Вы — на обычном. Т.е. ТП заменяет весь зоопарк обычных управляющих операторов. Вот и еще одна особенность автоматного программирования.
Код, в котором отсутствует операция && представлен листингом 5. Вы же ведете речь о Qt-шном варианте. Я так не программирую. Я — как на листинге 5. У меня в слотах, которые отрабатывают кнопки, есть только установка переменных входов автомата. Т.е. операций типа && нет и в помине.
Интерпретатор, возможно, работает, как Вы и говорите — последовательно. Но это всего лишь Ваше предположение и не более того. Как он там работает — одному разработчику этого интерпретатора известно ;) Для меня главное, чтобы эти стрелочки, которые я считаю параллельными, или множество входов и выходов автомата, которые я считаю параллельными, отработали параллельно. Дело в том, что есть признаки, которые позволяют обнаружить нарушение параллелизма их работы, но об этом я напишу отдельно. Поверьте, все работает параллельно — не придерешься! :)
Символы кодируют информацию, которая, безусловно, поступает последовательно. Но это относится только к одному входу автомата. У автомата, имеющего множество каналов, по ним (каналам) информация поступает параллельно и, кстати, выдается тоже параллельно. Вот в блок-схемах, да, обработка идет последовательно. Так, как это запрограммировано ее управлением, т.е. управляющими операторами языка.
Автоматное программирование не может быть из каменного века просто потому, что, строго говоря, его пока нет, как и не было (кроме ВКПа, конечно). Даже «великолепный MATLAB» его реализует лишь частично. И это я тоже собираюсь обсудить и показать. Но пока ближайшая тема — вложенные модели автоматов. А вот за ней, возможно, речь пойдет и о параллелизме. Но это будут уже сети автоматов. А пока надо завершить обсуждение модели отдельного автомата, как модели отдельного [последовательного] процесса.
По поводу отказа. Да оно только проявляется. Лишь недавно библиотеки стали включать моделирование автоматов (пусть коряво, но хоть так). Лишь недавно MATLAB сделал визуальное программирование на автоматах и т.д. и т.д. Да та же SWITCH технология «имени Шалыто» стала им рекламироваться лишь с 90-х годов. Какой тут каменный век? Можно сказать, — свежак!
Упс — ошибка, опечатка! В коде на переходах s1->s0 вместо y0() надо поставить y2();
Кстати, кто там все мой код «минусует»!? За что, интересно?
Sign up to leave a comment.

Articles