Show that the following problem is decidable 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?
 A: Yes, it is decidable, because no language can contain all the odd-length strings in $ \Sigma^*$ but no string consisting only of a's.
A: 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.}}$
A: The problem is decidable, but I think the question is being misinterpreted in some of these answers.  Here's the question again:

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\text{'s?}$  ($\varepsilon$ is assumed to consist only of $a\text{'s.)}$

The decision procedure is supposed to take a regular expression $\alpha$ as input, and determine whether the language $L$ defined by $\alpha$ has two properties:

  
*
  
*$L$ contains all the odd-length strings in $ \Sigma^*,$
  
  
  and

  
*$L$ contains no string consisting only of $a$'s.
  

If the language defined by $\alpha$ satisfies both 1 and 2, the decision procedure should output "Yes".  Otherwise, the decision procedure should output "No."
But no language can satisfy both these properties.  If $L$ satisfies Property 1, then it contains, for example, the string $"\!a\!"$ (since that's an odd-length string, and $L$ contains all odd-length strings).  But that means that it can't satisfy Property 2 (because we've exhibited a string consisting only of $a\text{'s}$ that belongs to $L.)$
So the decision procedure is simply:

No matter what the input $\alpha$ is, answer "No."

(The language defined by $\alpha$ cannot satisfy both 1 and 2, since no language can satisfy both 1 and 2.)

Conceivably the problem was misphrased.  Define: 
\begin{align}&S=\lbrace x \in \Sigma* \mid\text{ the length of }x\text{ is odd}\rbrace,
\\&T=\lbrace x \in \Sigma* \mid x\text{ consists only of }a\text{'s}\rbrace
\\&L_\alpha=\text{ the language defined by }\alpha.
\end{align}
As phrased, the problem asks us to test whether the following statement holds: $L_\alpha \supseteq S \,\land\, L_\alpha\cap T = \emptyset.$  (But this is a statement that's always false, no matter what $L_\alpha$ is.)
Maybe it was intended to ask us to test whether $L_\alpha \supseteq S\setminus T$ (or even some other interpretation — it's hard to guess what someone might have meant), but that's not what it says.
A: We can draw the DFA for strings of even length and draw another DFA for strings consisting of a only($a^*$) and then combine them to get a composite DFA.Then we can complement the obtained DFA to get the desired set.As we can draw the DFA we can also the Halting turing machine.Therefore, the following problem is decidable.
