Show that the following problem is decidable

Question

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?

Answer 1

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.}}$

Answer 2

Yes, it is decidable, because no language can contain all the odd-length strings in $ \Sigma^*$ but no string consisting only of a's.

Answer 3

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:

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

and

2. $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.