2
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ What's $\varepsilon$? $\endgroup$
    – Evan Aad
    Oct 21, 2016 at 10:49
  • $\begingroup$ @EvanAad: $\varepsilon$ is standard notation for the empty string $\endgroup$ Oct 21, 2016 at 10:51
  • 2
    $\begingroup$ It should mean exactly what it says, that the empty string is counted as a string consisting only of $a$s $\endgroup$ Oct 21, 2016 at 10:52
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 21, 2016 at 11:03
  • 1
    $\begingroup$ 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). $\endgroup$ Oct 21, 2016 at 14:52

4 Answers 4

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
16
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 21, 2016 at 10:56
  • 1
    $\begingroup$ 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$? $\endgroup$ Oct 21, 2016 at 11:36
  • 1
    $\begingroup$ 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). $\endgroup$ Oct 21, 2016 at 14:50
  • 1
    $\begingroup$ if $B\subset A$ it does not necessarily mean that $A$ contains no strings of the form $a^*$. For example, $B\subset \Sigma^*$. $\endgroup$
    – kagof
    Oct 22, 2016 at 1:21
  • 1
    $\begingroup$ @evanAad that looks correct to me! $\endgroup$
    – kagof
    Oct 22, 2016 at 3:55
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .