Is a set consisting of strings such that x is of prime length or x is of odd length regular? What about if x is prime length or x is even length?
My intuition says no because $L_p = \{x | |x| is prime\}$ is not regular.
$\begingroup$ $\endgroup$
0 
New contributor
Elijah Heimsoth is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
"Prime length or odd length" is equivalent to "odd length or length 2" which is pretty clearly regular.
For the other one, suppose you had a finite state machine that could recognize the language "prime length or even length". Think about a way you could modify it into a machine which recognizes the language of strings of prime length, which would be a contradiction as you know. Hint: one way involves a new machine with twice as many states.
Alternatively, use the pumping lemma. Start with a string of sufficiently long prime length, that can be written as $axb$ such that $a x^n b \in L$ for all $n$. Show that you can choose $n$ such that $|a|+|b|+n|x|$ is odd and composite. (It may help to consider separately the cases where $|a|+|b|$ is odd and $|x|$ is even, and vice versa.)
