런타임에 DFA 만들기. 얼마나 많은 주?

Question

현재 언어에 대한 영어 설명을 취한 다음 해당 설명을 사용하여 해당 사양의 DFA를 만드는 프로그램을 작성 중입니다. 나는 특정 작업을 허용한다. example {w | w는 처음에는 01이라는 서브 문자열을 가짐} 및 짝수 홀수 서브 스트링, k 서브 스트링보다 덜 정확하거나 정확하게 같은 다른 옵션을 갖는다. 사용자는 또한 알파벳을 선택한다.

내 질문은 내가 얼마나 많은 주를 필요로하는지 어떻게 알 수 있습니까? 사용자가 내 알파벳과 규칙을 제공하기 때문에 런타임까지는 아무 것도 모른다. 이전에 DFA/전환 테이블을 만들었지 만 이러한 경우에는 DFA가 무엇인지 알았고 클래스에서이를 선언하거나 정적으로 설정할 수있었습니다. 나는 5 개의 tupil (Q, Σ, δ, q0, F)을 사용해야합니까? 아니면 다른 접근법을 취하고 있습니까? 문제 해결에 도움이된다면 고맙겠습니다.

Answer 1

내 질문은 내가 얼마나 많은 주를 필요로하는지 어떻게 알 수 있습니까?

그렇지 않습니다.

당신은 (Q, σ) ∈ (Q, Σ) Q ∈ BTW 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; 

의 쌍 std::unordered_map으로 전환 기능을 나타낼 수있는, (1)은 수용성 상태 위 DFA의 경우, 정확히 a (a + ba)를 허용 *