Создание DFA во время выполнения. Сколько штатов?
В настоящее время я работаю над программой, которая будет использовать описание языка на английском языке, а затем использовать описание для создания DFA для этих спецификаций. Я разрешаю определенные операции, пример {ш | w имеет подстроку 01 в начале} и другие параметры, такие как четная нечетная подстрока, больше или меньше, чем k подстрока и т. д. Пользователь также выбирает алфавит.
Мой вопрос: откуда мне знать, сколько штатов мне понадобится? так как пользователь дает мне мой алфавит и правила, я ничего не знаю до времени выполнения. Я создавал таблицы DFA / переходов ранее, но в тех случаях я знал, что такое мой DFA, и мог объявить его в классе или сделать его статическим. Должен ли я использовать 5 тупил (Q, ∑, δ, q0, F)? или другой подход? Любая помощь, решающая мою проблему, приветствуется.
Решение
Мой вопрос: откуда мне знать, сколько штатов мне понадобится?
Вы не будете.
Вы можете представить функцию перехода как std::unordered_map пар (q, σ) ∈ (Q, Σ) в q ∈ Q
using state = int;
using symbol = char;
using tranFn = std::unordered_map<std::pair<state, symbol>, state>;
// sets up transition function, the values can be read at runtime
tranFn fn;
fn[{0, 'a'}] = 1;
fn[{0, 'b'}] = 2;
fn[{1, 'a'}] = 1;
fn[{1, 'b'}] = 0;
fn[{2, 'a'}] = 2;
fn[{2, 'b'}] = 2;
// run the dfa
state s = 0;
symbol sym;
while(std::cin >> sym)
s = fn[{s, sym}];
std::cout << s;
Кстати, если 1 является состоянием принятия в dfa выше, он принимает ровно a (a + ba) *
Другие решения
Других решений пока нет …