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

• What's $\varepsilon$? Oct 21, 2016 at 10:49
• @EvanAad: $\varepsilon$ is standard notation for the empty string Oct 21, 2016 at 10:51
• It should mean exactly what it says, that the empty string is counted as a string consisting only of $a$s Oct 21, 2016 at 10:52
• So an equivalent question is: given a finite automaton, can we effectively decide whether the language it accepts is the language specified? That seems more concrete to me. Oct 21, 2016 at 11:03
• I’ll repeat here a comment that I made under Evan Aad’s answer: There is more than one language over $\Sigma$ that contains all of the odd-length strings and and no string of the form $a^n$ ($n\ge 0$). One of these languages contains no even-length strings. Another contains all even length strings that contain at least one $b$. And so on. Thus, it’s not a matter of comparing $L(\alpha)$ with a single regular language (unless the OP stated the problem incorrectly). Oct 21, 2016 at 14:52

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

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

• The question asked whether, given a regular expression, it is possible to determine (effectively) whether the language of that regular expression is the language specified. It did not ask if every regular expression gives that language. Oct 21, 2016 at 10:56
• Thanks. This does seem to be the easiest approach to the problem. For your regular expressions, I might be misreading them, but which one would accept $abaaaaa$? Oct 21, 2016 at 11:36
• There is more than one language over $\Sigma$ that contains all of the odd-length strings and and no string of the form $a^n$ ($n\ge 0$). One of these languages contains no even-length strings. Another contains all even length strings that contain at least one $b$. And so on. Thus, it’s not a matter of comparing $L(\alpha)$ with a single regular language (unless the OP stated the problem incorrectly). Oct 21, 2016 at 14:50
• if $B\subset A$ it does not necessarily mean that $A$ contains no strings of the form $a^*$. For example, $B\subset \Sigma^*$. Oct 22, 2016 at 1:21
• @evanAad that looks correct to me! Oct 22, 2016 at 3:55

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

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

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.