I must show that the following problem is decidable: Given Σ={a,b} \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?

– Evan Aad

2 days ago

@EvanAad: ε\varepsilon is standard notation for the empty string

– Carl Mummert

2 days ago

2

It should mean exactly what it says, that the empty string is counted as a string consisting only of aas

– Carl Mummert

2 days ago

1

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.

– Carl Mummert

2 days ago

1

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 ana^n (n≥0n\ge 0). One of these languages contains no even-length strings. Another contains all even length strings that contain at least one bb. And so on. Thus, itâ€™s not a matter of comparing L(α)L(\alpha) with a single regular language (unless the OP stated the problem incorrectly).

– Brian M. Scott

2 days ago

=================

3 Answers

3

=================

Let LL be the regular language defined by the regular expression α\alpha. The question you want to solve is to know whether (Σ2)∗Σ⊆L(\Sigma^2)^*\Sigma \subseteq L and L∩a∗=∅L \cap a^* = \emptyset.

Given(∗){}^{(*)} two regular languages L1L_1 and L2L_2, the questions whether L1L_1 contains L2L_2 and whether L1L_1 and L2L_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 LL. The condition L∩a∗=∅L \cap a^* = \emptyset means that you can never reach a final state by using only aa-transitions. In other words, all the states qnq_n (including the initial state q0q_0) defined by q0an→qnq_0 \xrightarrow{a^n} q_n are nonfinal. The condition (Σ2)∗Σ⊆L(\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).

(∗)A regular language can be given by a finite DNA, by a finite DFA or by a regular expression.{}^{(*)}\scriptstyle{\text{A regular language can be given by a finite DNA, by a finite DFA or by a regular expression.}}

There are standard algorithms to convert one of the forms to the other ones.\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.

2

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.

– Carl Mummert

2 days ago

1

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

– Carl Mummert

2 days ago

1

There is more than one language over Σ\Sigma that contains all of the odd-length strings and and no string of the form ana^n (n≥0n\ge 0). One of these languages contains no even-length strings. Another contains all even length strings that contain at least one bb. And so on. Thus, itâ€™s not a matter of comparing L(α)L(\alpha) with a single regular language (unless the OP stated the problem incorrectly).

– Brian M. Scott

2 days ago

1

if B⊂AB\subset A it does not necessarily mean that AA contains no strings of the form a∗a^*. For example, B⊂Σ∗B\subset \Sigma^*.

– kag

2 days ago

1

@evanAad that looks correct to me!

– kag

yesterday

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 Σ={a,b} \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?a\text{‘s?} (ε\varepsilon is assumed to consist only of a’s.)a\text{‘s.)}

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

LL contains all the odd-length strings in Σ∗, \Sigma^*,

and

LL contains no string consisting only of aa’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 LL satisfies Property 1, then it contains, for example, the string “a””\!a\!” (since that’s an odd-length string, and LL 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}a\text{‘s} that belongs to L.)L.)

So the decision procedure is simply:

No matter what the input \alpha\alpha is, answer “No.”

(The language defined by \alpha\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}\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.L_\alpha \supseteq S \,\land\, L_\alpha\cap T = \emptyset. (But this is a statement that’s always false, no matter what L_\alphaL_\alpha is.)

Maybe it was intended to ask us to test whether L_\alpha \supseteq S\setminus TL_\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.