Question

Let is a regular expression describing a language containing at least one string w that has 111 as a substring $\left(\text{i.e.,}w=x111y \text{for} \text{some} x \text{and} y\right)\}$. Show that A is decidable.

Short answer

A is decidable.

Step-by-step solution

Explain DFA

DFArefers to deterministic finite automata. In DFA, there is only one path for a specific input from a current state to the next state.

Show that A is decidable

Consider the language $C=\left\{w\in \sum *|w \text{consists} 111 \text{as} \text{a} \text{substring}\right\}$. Consider that C is a regular language with the regular expression $\left(0\cup 1\right)*111\left(0\cup 1\right)*$ and is recognized by the following DFA, D_c.

Now, consider any regular expression with the alphabet $\sum .$If $C\cap L\left(R\right)=\varnothing$, then R generates a string having 111 as a substring, so $\left(R\right)\in A$. Also, if $C\cap L\left(R\right)=\varnothing$, then R does not generate any string having 111 as a substring, thus . By the Kleen’s Theorem, since L(R) is described by the regular expression R, L(R) must be a regular language. Since C and L(R) are regular languages, $C\cap L\left(R\right)$is regular since the class of regular languages is closed under intersection. Thus, $C\cap L\left(R\right)$has some DFA $D_{C\cap L\left(R\right)}.$The theorem 4.4 shows that is decidable, so there is a Turing machine H that decides the $E_{DFA}$. Apply TM H to $D_{C\cap L\left(R\right)}$to determine if $C\cap L\left(R\right)=\varnothing$. Putting this all together gives us the following Turing machine T to decide A : T = “On input

where R is a regular expression:

1. Convert Rinto a DFA using the algorithm in the proof of the Kleene’s Theorem.

2. Construct a DFA, $D_{C\cap L\left(R\right)}$ for language $C\cap L\left(R\right)$ from the DFAs D_c and D_R.

3. Run TM H that decides $E_{DFA}$on input .

4. If Haccepts, reject. If Hrejects, accept.”

Therefore, the Turing machine H decides A . Hence, it has been shown that A is decidable.