1

Minha intenção é definir uma função que permita simular a execução de um autômato finito determinista (DFA) dado.

De acordo com a definição formal um DFA é a 5-upla M = (Q, Σ, δ, q0, F) em que:

  • Q é o conjunto de estados da máquina.
  • Σ é um conjunto de símbolos denominado alfabeto, que compõem a entrada.
  • δ é uma função de transição definida por δ : Q x Σ → Q.
  • q0 ∈ Q é o estado inicial.
  • F ⊆ Q é o conjunto de estados finais.

Eis a função que imaginei:

typedef std::set<unsigned> StateSet;
typedef std::set<char> Alphabet;
typedef std::list<std::function<unsigned(const unsigned&, const char&)>> TransitionTable;

void RunAutomaton (const StateSet &states, const Alphabet &alphabet, const TransitionTable &table, const unsigned &initState, const SateSet &finalStates) {
    // Executa o autômato...
}

No entanto esse código não dá segurança nenhuma sobre os parâmetros da função. Eu queria ter a certeza de que a tabela tivesse os valores corretos, i.e, os caracteres e estados da tabela de transição fossem apenas caracteres presentes no alfabeto e na lista de estados, respectivamente. Também não há como ter certeza de que a lista de estados finais é um subconjunto da lista de estados original (primeiro argumento); e o estado inicial pertença à lista de estados.

Há alguma maneira de definir uma função de tal forma que eu tenha certeza que os argumentos passados estejam todos corretos sem que eu precise fazer verificações à mão?

2 Respostas 2

0

Você pode limitar os valores que uma variável pode assumir através de enumerações fortemente tipadas.

Este é um conceito introduzido no C++11 para fortalecer a restrição dos valores enumerados para pertencentes ao conjunto declarado. (antigamente, desde o C, enumerações podiam ser implicitamente convertidas de inteiros, por exemplo)

Dada a declaração:

enum class Alfabeto {Alfa, Beta, Gama};

Variáveis do tipo Alfabeto só podem assumir os valores enumerados, por exemplo:

Alfabeto var1 = Alfabeto::Gama;

E não se pode declarar valores fora do conjunto:

Alfabeto var2 = 3; // erro:  cannot convert 'int' to 'Alfabeto'
Alfabeto var3 = Alfabeto::Omega; // erro: 'Omega' is not a member of 'Alfabeto'

Depois de declarada a enumeração, Alfabeto é tratado como um tipo específico de variável, e pode ser usado como argumento de funções:

void func(Alfabeto x)
{
    switch(x)
    {
        case Alfabeto::Alfa:
            std::cout << "Entrada alfa" << std::endl; return;
        case Alfabeto::Beta:
            std::cout << "Entrada beta" << std::endl; return;
        case Alfabeto::Gama:
            std::cout << "Entrada gama" << std::endl; return;
    }
}

A enumeração também pode ser usada em contêineres, como no seu exemplo:

std::vector<Alfabeto> vec;
vec.push_back(Alfabeto::Alfa);
vec.push_back(Alfabeto::Beta);
vec.push_back(Alfabeto::Gama);

Segue um exemplo completo:

#include <iostream>
#include <vector>

enum class Alfabeto {Alfa, Beta, Gama};

void func(Alfabeto x)
{
    switch(x)
    {
        case Alfabeto::Alfa:
            std::cout << "Entrada alfa" << std::endl; return;
        case Alfabeto::Beta:
            std::cout << "Entrada beta" << std::endl; return;
        case Alfabeto::Gama:
            std::cout << "Entrada gama" << std::endl; return;
    }
}

void func2(std::vector<Alfabeto> v)
{
    for(auto x:v)
        {
            func(x);
        };
}

int main()
{
    std::vector<Alfabeto> vec;
    vec.push_back(Alfabeto::Alfa);
    vec.push_back(Alfabeto::Beta);
    vec.push_back(Alfabeto::Gama);
    func2(vec);
}

O exemplo pode ser conferido online neste link.

-1

Com certeza existe mais de uma maneira de modelar um autômato (finito determinístico), mas acho que você poderia tentar algo assim

struct State
{
   int id;
};

using States = std::set<State>;
States states
{
   { 1 },
   { 2 },
   { 3 },
   // ...
};

States finalStates
{
   { 1 },
   // ...
};

struct Symbol
{
   char value.
};
using Alphabet = std::set<Symbol>;
Alphabet alphabet
{
   { 'a' },
   { 'b' },
   { 'c' },
   // ...
};

struct Transition
{
   State current;
   Symbol input;
   State next;
}

using TransitionTable = std::vector<Transition>;
TransitionTable ttable
{
   { {1} , { 'a' }, { 2 } },
   { {2} , { 'c' }, { 3 } },
   // ...
};

State q0 { 0 ];

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .