I must show that the following problem is decidable: Given $ \Sigma = \{a,b\}$ and $\alpha$ a regular expression, is it true that the language defined by $\alpha$ contains all the odd-length strings in $ \Sigma^*$ but no string consisting only of a's? ($\varepsilon$ is assumed to consist only of a's.)
I would say the answer to the question is false, however I don't know how to show that it is decidable.
From what I understand, I can determine whether a problem is decidable based on whether it finishes execution or runs in an infinite loop forever. What I don't understand however is the context of this problem, since it is not an actual program. I feel like there is not enough information here to draw a conclusion. There is something related to decision procedures required to solve this (Emptiness, Totality, etc not sure which one however). How can I determine whether this problem is decidable?
Best Answer
Let $L$ be the regular language defined by the regular expression $\alpha$. The question you want to solve is to know whether $(\Sigma^2)^*\Sigma \subseteq L$ and $L \cap a^* = \emptyset$.
Given${}^{(*)}$ two regular languages $L_1$ and $L_2$, the questions whether $L_1$ contains $L_2$ and whether $L_1$ and $L_2$ are disjoint are decidable. Thus your question is decidable by generic arguments. However, in this special case, it is relatively easy to decide. Consider the minimal complete DFA accepting $L$. The condition $L \cap a^* = \emptyset$ means that you can never reach a final state by using only $a$-transitions. In other words, all the states $q_n$ (including the initial state $q_0$) defined by $q_0 \xrightarrow{a^n} q_n$ are nonfinal. The condition $(\Sigma^2)^*\Sigma \subseteq L$ is equivalent to stating that every path of odd length issued from the initial state terminates in a final state. Again, this condition can be easily checked on the DFA (this is a simple graph argument that I let you formulate precisely).
${}^{(*)}\scriptstyle{\text{A regular language can be given by a finite DNA, by a finite DFA or by a regular expression.}}$ $\scriptstyle{\text{There are standard algorithms to convert one of the forms to the other ones.}}$