1
$\begingroup$

I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing.

Be A = {(R)|R it is a regular expression that describes a language containing at least a w string that has 111 as a substring (that it is, w=x111y to some x and some y)}. Show that A it is decidible

Answer: Create a turing machine P, this machine receives a pair where R is the regular expression in question and W is the set of all the strings of the form x111y. P converts R into a NFA called NFAR. It sends the pair to a TM N that acts as a subrotine of it. N will convert NFAR into a DFA called DFAR. Then inside this machine N, there is a turing machine M inside it, also acting as a subrotine. It sends the pair to M. When M receives its input, it will first determines whether it properly represents a DFA DFAR an a set of strings W. If not, it will reject, and as a result, so will N and then P. Otherwise, It will start to simulate DFAR over the first string w(i) of W (where i=0,1,2... n° last input string). If DFAR accepts, M halts in the accept state, and so will N and then P. Otherwise M will continue to loop through all the strings of W. If it reaches the last w(i) and it is not accepted, M will halt in the refect state and so will N and then P.

My fear is that the number of strings to be tested is infinite, so M could enter in a loop?

$\endgroup$
  • $\begingroup$ I believe your description of the proposed solution is too complex (too low-level). Perhaps something along the lines of reducing the RE to the minimal DFA, and then checking if it accepts anything with 111 (look at its transitions). $\endgroup$ – vonbrand Jan 25 '14 at 13:42
  • $\begingroup$ @vonbrand How exactly do you check that? Rather, I claim that you can also check whether the regular expression accepts any word containing exactly $10$ ones, at least $3$ of which appear in odd indices, and having even length. Using the same method. $\endgroup$ – Yuval Filmus Jan 26 '14 at 1:26
2
$\begingroup$

When showing that something is decidable, we don't usually invoke the concept of Turing machines. Rather, we use the Church–Turing thesis that states that informally described algorithms are realizable by Turing machines. Even when describing Turing machines, there is no need to describe subroutines—that's a programming concept that you are misusing here. Finally, there is absolutely no need to add consistency checks to your code! This code isn't going to be compiled. You can assume that it is bug-free. That's why we only give an informal description, in which these messy details are missing.

Another mistake you make in describing your program is the input $W$. This input is constant, and so there is no need to include it. Also, you haven't explained how you represent $W$: the set of all strings containing $111$ is infinite.

Let me rephrase your algorithm informally. The algorithm gets as input a regular expression $r$, which it then converts to an equivalent DFA (there is no need to explicitly go through the intermediary NFA; we already know that regular expressions can be converted to equivalent DFAs). Then it goes over all strings containing $111$ in lexicographic order, and if the DFA accepts any of them, it outputs Yes.

Do you see the problem with your algorithm? It never outputs No. When the answer is No, it never halts. So you haven't shown that the problem is decidable, only that it is semidecidable (i.e. recursively enumerable).

Let me offer a different direction. Suppose I gave you a regular expression, and asked you whether the language it describes has a word containing $111$. How would you answer that? Can your answer be implemented mechanically? If so, you've found an algorithm and shown that the problem is decidable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "we don't usually invoke the concept of Turing machines" -- depends on your level, I guess. In any case, using WHILE languages or C-style pseudocode can savely be used instead of TMs (by proof, not thesis). $\endgroup$ – Raphael Jan 25 '14 at 16:30
  • $\begingroup$ I found the first paragrapher of your answer confusing, because all I did is exactly what the book that I was using used in others decidability cases. All the stuff about subrotine, converting to NFA and DFA was there. Anyway, when I first thought about it, I thought there would be strings of all kinds, not only ones with 111 as a substring. I also don't understand why the set of all strings is infinite, aren't they 5 symbols strings? About the other direction, my answer would be to check the regular expression itself and see if it has a 111 substring $\endgroup$ – user2752471 Jan 26 '14 at 0:09
  • $\begingroup$ (1) You should follow your book when it doubt, it's a question of style, and as Raphael mentions, it depends on the class's place in the curriculum. (2) The set of strings containing 111 is infinite. I count infinitely many of them. (3) That would fail on $(0+1)(0+1)(0+1)$. Think about decidable properties of regular languages (the languages in question are the one given by the regular expression, and the one consisting of all words containing $111$). $\endgroup$ – Yuval Filmus Jan 26 '14 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.