I am attempting to solve the following problem:
Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of even length. Show how to construct a deterministic finite automata, $M'$ accepting $E$.
I feel I nearly have a solution, but I am not quite there. This is my approach:
In order to construct $M'$ we may duplicate the states of $M$, so that we may have $q_{Meven}$ and $q_{Modd}$. Rather than going from $q_1$ to $q_2$, we would go from $q_{1odd}$ to $q_{2even}$. Only accept states in $F_M$ and $Q_{even}$ would be accepted.
So, $M'=(Q,\Sigma,\delta,q_0,F)$, where:
$Q=Q_{even}\cup Q_{odd}$, where $Q_{even}=Q_{odd}=Q_M$
$q_0=q_{0even}$, and
$F=F_{M}\cap Q_{even}$.
$\delta = $
-
if $(q_n\in Q_{odd})\space q_{n\space odd}\rightarrow q_{n+1\space even} $
-
if $(q_n\in Q_{even})\space q_{n\space even}\rightarrow q_{n+1\space odd} $
Is this the correct approach? Are my terms (such as $Q_{even}$) sufficiently defined? If not how would I define them? Does my transition function make any sense?
Automata theory is fairly new to me, so while I might have the right idea in my head, it is difficult to translate that to the formal language used in automata theory. Your help is much appreciated.
Best Answer
Your approach is fine. You could tidy up the definitions a bit to make it a bit clearer, but I had no trouble figuring out what you were doing.
Using primes for the parts of the new automaton, you might, for instance, let $Q'=Q\times\{0,1\}$, $Q_0'=Q\times\{0\}$, and $Q_1'=Q\times\{1\}$; my $Q_0'$ is your $Q_{even}$, and my $Q_1'$ is your $Q_{odd}$. I’ll let $F'=(F\times\{0\})\cap Q_0'$ and $q_0'=\langle q_0,0\rangle$. Finally, I’ll define
$$\delta':Q'\times\Sigma\to Q':\big\langle\langle q,i\rangle,\sigma\big\rangle\mapsto\big\langle\delta(\langle q,\sigma\rangle),1-i\big\rangle\;.$$
Then $M'=\langle Q',\Sigma,\delta',q_0',F'\rangle$ does what you want (and is really just a more formal, carefully presented version of your machine).
(By the way, automata is plural: the singular is automaton.)