Constructing a finite automata from a subset of its language

Question

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.

Answer 1

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.)

Answer 2

Before computing an automaton, you may first try to obtain a formal description of the language you are looking for. Here, the language $E$ is the intersection of $L(M)$ and of the set of words of even length. Formally $$ E = L(M) \cap (\Sigma^2)^* $$ Now, it is easy to find a DFA accepting $(\Sigma^2)^*$ and hence, the problem reduces to find an automaton accepting the intersection of two regular languages, given a DFA recognizing each of them. You certainly have learnt this algorithm.

Doing so, you will observe that you arrive exactly at the solution proposed by Brian M. Scott.