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?
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!