How to limit a function parameter so that it is an element of a set?

Question

My intention is to define a function that allows to simulate the execution of a deterministic finite automaton (DFA) datum.

According to the formal definition a DFA is the 5-upla M = (Q, Σ, δ, q₀, F) in which:

• Q is the set of machine states.
• Σ is a set of symbols called alphabet, making up the entry.
• δ is a transition function defined by δ : Q x Σ Q.
• q₀ Q is the initial state.
• F Q is the set of final states.

Here’s the function I imagined:

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...
}

However this code does not give any security on the parameters of the function. I wanted to make sure that the table had the correct values, i.e, the characters and states of the transition table were only characters present in the alphabet and the list of states, respectively. There is also no way to be sure that the list of final states is a subset of the original list of states (first argument); and the initial state belongs to the list of states.

Is there any way to define a function in such a way that I can be sure that the past arguments are all correct without me having to do any checks by hand?

Answer 1

You can limit the values a variable can assume through strongly typed enumerations.

This is a concept introduced in C++11 to strengthen the restriction of the listed values to those belonging to the declared set. (formerly, from C, enumerations could be implicitly converted from integers, for example)

Given the statement:

enum class Alfabeto {Alfa, Beta, Gama};

Variables of the type Alfabeto may only take the values listed, for example:

Alfabeto var1 = Alfabeto::Gama;

And you can’t declare values outside the set:

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

After the enumeration has been declared, Alfabeto is treated as a specific type of variable, and can be used as argument functions:

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;
    }
}

Enumeration can also be used in containers, as in your example:

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

Here is a complete example:

#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);
}

The example can be checked online at this link.

Answer 2

Surely there is more than one way to model an automaton (deterministic finite), but I think you could try something like this

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 ];