Negation of Finite State Machine
Jump to navigation
Jump to search
Theorem
Let $F = \tuple {S, A, I, \Sigma, T}$ be a finite state machine.
Then there exists a finite state machine $F'$ such that $\map L {F'} = \map \complement {\map L F}$.
Proof
Construct $F' = \tuple {S, S \setminus A, I, \Sigma, T}$.
The state transitions are identical to those of $F$.
However, when the input word is exhausted, the final state is an accepting state if and only if it is not an accepting state in $F$, as required.
$\blacksquare$