I have this question about if the decidability of an regular expression and woul
ID: 654496 • Letter: I
Question
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
Explanation / Answer
When showing that something is decidable, we don't usually invoke the concept of Turing machines. Rather, we use the Church