1
$\begingroup$

Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?

Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, F \}$, if $w = uv$ and the state of $A$ on input $w$, after scanning $u$ is $q_i$ (when the head is at the beginning of subword $v$); and $A' = \{ Q, \Sigma, \delta, q_i, F \}$ then $w \in L(A)$ if and only if $v \in L(A')$

$\endgroup$
1
  • 2
    $\begingroup$ It seems so obvious that I doubt anyone would name it or call it a theorem. $\endgroup$ – David Richerby Apr 20 '19 at 20:26
1
$\begingroup$

Actually I think I have spotted this property in a book. It uses the "extended" transition relation $\delta^*$, i.e., for strings rather than single letters.

Other properties you would expect $\delta^*$ to satisfy can be derived from our definition. For example, a natural generalization of the recursive statement in the definition is the formula $$\delta^*(q,xy) = \delta^*(\delta^*(q,x),y))$$ which is true for every state $q$ and every two strings $x$ and $y$ in $\Sigma^*$. The proof is by structural induction on $y$ and is similar to the proof [...] in Example 1.27.

John C. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 4th edition, c2011. Page 54.

I hope you agree with me that this matches the "machine" terminology you use in your question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.