I am currently working on a program that will take a English description of a language and then use the description to create a DFA for those specs. I allow certain operations, example {w | w has the sub string 01 in the beginning} and other options such as even odd sub string, more less or exactly than k sub string, etc. The user also chooses the alphabet.
My question is how would i know how many states I will need? since the user gives me my alphabet and rules I don't know anything until run time. I have created DFA's/transition tables before, but in those cases I knew what my DFA was and could declare it in a class or have it static. Should I be using the 5 tupil (Q, ∑, δ, q0, F)? or taking a different approach? Any help wrapping my head around the problem is appreciated.
My question is how would i know how many states I will need?
You won't.
You can represent the transition function as std::unordered_map of pairs of (q, σ) ∈ (Q, Σ) to 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;
btw, if 1 is the accepting state in the dfa above, it accepts exactly a(a + ba)*