在运行时间创建 DFA。有几个州？

Question

我目前正在开发一个程序，该程序将采用一种语言的英文描述，然后使用该描述为这些规范创建 DFA。我允许某些操作，例如 {w | w开头有子串01}和其他选项如偶数子串、比k子串少或刚好等。用户还可以选择字母表。

我的问题是我怎么知道我需要多少个州？因为用户给了我我的字母表和规则，所以我在运行之前什么都不知道。我以前创建过 DFA's/transition 表，但在那些情况下我知道我的 DFA 是什么并且可以在 class 中声明它或将其设为静态。我应该使用 5 tupil (Q, ∑, δ, q0, F) 吗？还是采取不同的方法？感谢任何帮助我解决这个问题的帮助。

Answer 1

My question is how would i know how many states I will need?

你不会的。

您可以将转换函数表示为 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)*

在运行时间创建 DFA。有几个州？

Creating a DFA at run time. How many states?

c++

dfa

在 运行 时间创建 DFA。有几个州？

Creating a DFA at run time. How many states?

c++

dfa

在运行时间创建 DFA。有几个州？