Regular Languages Algorithm? I need help proving the following question:
Let $L$ be any regular language on $\sum{a,b}$. Show that an algorithm exists for determining if L contains any strings of even length. 
So far, I know that since $L$ is regular, then there exists a dfa. 
And if $L$ contains no even-length strings, then $L$ intersection $L ((aa + ab + ba + bb)*)$ = the empty set.
How do i show that an algorithm exists?
 A: The best proof that such algorithm exists is to present it ;-)
First of all, since you want to answer if language $L$ contains any word of even length, and not required to give an example of such word, you can map all the letters to a single symbol. Then you could just try all the words of length $2k \leq 2(n + 1)$. 
In fact, if you are given an automaton, you could take word $a^n$ and while running it note if you were at any accepting state after even letter (that is, you don't need to try all the words, because shorter words $a^{2k}$ are prefixes of the $a^n$).
Good luck!
A: Conputing $L \cap (A^2)^*$ is the generic solution, but given the very specific form of your problem, there is an alternative way. I will try to explain it on an example. Consider the following automaton $\mathcal{A}$ 
(source: jep at www.irif.fr)
Its transitions are given in the following table
\begin{align*}
 &|\ \ 1\ \ 2\ \ 3\ \ 4\ \ 5\\
\hline
a &|\ \ 2\ \ 3\ \ 4\ \ 3\ \ 4\\
\hline
b &|\ \ 0\ \ 5\ \ 4\ \ 3\ \ 4 
\end{align*}
Now, consider the set $\{aa, ab, ba, bb\}$ of all words of length $2$ as a new alphabet and compute the transitions generated by these four words.
\begin{align*}
 &|\ \ 1\ \ 2\ \ 3\ \ 4\ \ 5\\
\hline
aa &|\ \ 3\ \ 4\ \ 3\ \ 4\ \ 3\\
ab &|\ \ 5\ \ 4\ \ 3\ \ 4\ \ 3\\
ba &|\ \ 0\ \ 4\ \ 3\ \ 4\ \ 3\\
bb &|\ \ 0\ \ 4\ \ 3\ \ 4\ \ 3
\end{align*}
This leads you to the following automaton $\mathcal{A}_2$ 
(source: jep at www.irif.fr)
which, after reduction (state $3$ is useless), gives you the automaton $\mathcal{A}_3$ 
(source: jep at www.irif.fr)
which recognizes exactly the words of even length accepted by $\mathcal{A}$.
If you just want to know whether $L$ contains some word of even length, you could just use a depth-first search algorithm in the automaton $\mathcal{A}_2$ to see whether or not you reach a final state.
