이 언어를 기반으로 DFA 구성
허락하다 $L \subseteq \Sigma^*$ 모든 알파벳의 언어 $\Sigma$. 허락하다$move(L)$ 마지막 문자를 사용하도록 모든 문자열을 포함하는 언어를 설명하십시오. $x \in L$ 그리고 앞쪽에 놓습니다.
DFA를 구성하는 방법 $A$ ...에 대한 $move(L)$?
먼저 L 용 DFA가 어떤 것인지 살펴 보았습니다.
- 말하다 $s = s_0 s_1 s_2 ... s_n$ 어디 $s_i \in \Sigma$ 이 DFA에서 허용하는 문자열입니다.
- 그것은 국가의 경로를 따라 갈 것입니다 $q_0q_1...q_n$. 마지막 상태를 처음으로 전환했습니다.$A$ 하지만 뭔가 옳지 않다는 말이있어서 어떻게 진행해야할지 모르겠습니다.
답변
허락하다 $\ A=\big(Q,\Sigma, \delta, q_0, F\big)\ $ 허용하는 DFA $\ L\ $. 하자 \ {정렬} Q '& = \ 큰 (\ 시그마 \ 배 Q \ 대) \, \ 컵 \ 큰 \ {q_0'\ 큰 \} \\ F '& = \ 큰 \ {(S, Q)를 시작 \ in \ Sigma \ times Q \, \ big | \, \ delta (q, s) \ in F \ big \} \\ \ delta '(q', s) & = \ cases {(s, q_0) & if$\ q'=q_0'$\\ \ big (\ 시그마, \ delta (q, s) \ big) & if $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \ end {align} 그런 다음$\ S'=\big(Q',\Sigma, \delta', q_0', F'\big)\ $ 허용하는 DFA입니다. $\ move(L)\ $.
만약 $\ \xi\in\Sigma^*\ $, 및 $\ q_n\ $ 상태입니다 $ A\ $ 문자열을 처리 한 후 $\ \xi\ $, 다음 $\ \big(s_0,q_n\big)\ $ 상태가 될 것입니다 $\ A' $ 문자열을 처리 한 후 $\ s_0\xi\ $, 및 $\ \big(s_0,q_n\big)\in F'\ $ 경우에만 $\ \delta(q_n,s_0)\in F\ $-그건, $\ A'\ $ 문자열을 받아들입니다 $\ s_0\xi\ $ 경우에만 $\ A\ $ 문자열을 받아들입니다 $\ \xi s_0\ $.
의견에서 OP의 쿼리에 응답
일반적으로 해당 언어의 최소 상태 DFA는 $\ L\ $ 최소 상태 DFA보다 더 적은 상태를 $\ move(L)\ $이므로 DFA를받은 경우 $\ L\ $ 항상 DFA를 구성 할 수있는 것은 아닙니다. $\ move(L)\ $동일한 상태 집합이 있습니다. 만약\begin{align} L=\ &\big\{a^{n_1}b^{n_2}c^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\\ \cup &\big\{a^{n_1}b^{n_2}d^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\\ \cup &\big\{a^{n_1}b^{n_2}e^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge1\,\big\}\ , \end{align} 예를 들어, $5$-허용하는 상태 DFA $\ L\ $. 하나,\begin{align} move(L)=\ &\big\{ca^{n_1}b^{n_2}c^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\\ \cup &\big\{da^{n_1}b^{n_2}d^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\\ \cup &\big\{ea^{n_1}b^{n_2}e^{n_3}\,\big|\,n_1\ge0, n_2\ge0, n_3\ge0\,\big\}\ , \end{align} 허용하는 DFA를 표시하는 것은 어렵지 않습니다. $\ move(L)\ $ 최소한 $7$상태 ( 예를 들어 Myhill-Nerode 정리 사용 ).
만약 $\ \epsilon\in L\ $?
Dromniscience의 답변 과 아래 LetmeKnow 의 의견은 위의 답변이 암시 적으로 (그리고 실수로 내 부분에서) 반드시 정당화되지 않는 가정을한다는 사실을 경고했습니다. 즉, 이동 작업이 빈 문자열을 제거 할 것이라는 가정을 합니다.$\ \epsilon\ $ 그것이 일어난다면 $\ L\ $. 때문에$\ q_0'\not\in F'\ $ 위의 정의에서 $\ A'\ $ 빈 문자열 $\ \epsilon\ $ 허용되는 언어로되어있을 수 없습니다. $\ A'\ $.
그러나 OP는 이동 작업이 빈 문자열을 처리 하는 방법을 지정하지 않기 때문에 다음 과 같이 가정하는 것이 정당하지 않은 것 같습니다.$\ \epsilon\not\in move(L)\ $ 할때는 언제나 $\ \epsilon\in L\ $. 대신에$\ \epsilon\in L\ \implies\epsilon\in move(L)\ $ 다음의 정의 $\ A'\ $다음과 같이 수정해야합니다. \ begin {align} Q '& = \ big (\ Sigma \ times Q \ big) \, \ cup \ big \ {q_0'\ big \} \\ F '& = \ cases {\ big \ {(s, q) \ in \ Sigma \ times Q \, \ big | \, \ delta (q, s) \ in F \ big \} & if$\ q_0\not\in F$\\ \ big \ {(s, q) \ in \ Sigma \ times Q \, \ big | \, \ delta (q, s) \ in F \ big \} \ cup \ big \ {q_0 '\ big \ }&만약 $\ q_0\in F$} \\ \ delta '(q', s) & = \ cases {(s, q_0) & if $\ q'=q_0'$\\ \ big (\ 시그마, \ delta (q, s) \ big) & if $\ q'=(\sigma,q)\in\Sigma\times Q\ $.} \ end {align}
실제로 마지막 전환을 앞으로 이동할 필요는 없습니다. 대신 첫 글자를 기억하고 원래 DFA에서 최종 상태로 이어질지 확인하는 것이 어떻습니까?
계속 읽기 전에 다시 생각해보십시오. 원래 DFA를$L = \langle Q, \Sigma, \delta, q_0, F\rangle$, 새 DFA를 구성 할 수 있습니다. $move(L) = \langle Q', \Sigma, \delta', q_{init}, F'\rangle$, 어디 \begin{align} Q' &= \{q_{init}\} \cup \Sigma \times Q \\ F' &= \{(a, q)\mid \delta(a, q)\in F\} \\ \delta'((a, q), b) &= (a, \delta(q,b)) \\ \delta'(q_{init}, b) &= (b, q_0) \\ \end{align} 이후 $\epsilon$ 절대 없다 $move(L)$, $F'$ 충분합니다.