Let $L$ be a regular language.

Let $L'=\{\sigma_1...\sigma_n|n\ge 1, \forall 1\le i\le n, \sigma \in \sum. \exists i: 1\le i\le n \quad\land\quad \exists u\in L: \sigma_1...\sigma_{i-1}u\sigma_{i+1}...\sigma_n\in L\}$.

Prove that $L'$ is regular.

First of all, as far as I understand if for example $L=\{abcxyzdef, xyz\}$ then a possible word in $L'$ is $abckdef$ if $\sum=\{a,b,c,d,e,f,k,x,y,z\}$.

The proof is:

Because $L$ is regular then exists a DFA that receives it: $A=\{\sum,Q,q_0,F,\delta \}$. We can build a DFA $B$ which will receive $L'$ as follows: $$ B=\bigg\{\sum, Q\times\{1,2\}\cup Q\times Q, (q_0, 1), F\times\{2\}, \mu \bigg\} $$

1) Because we need to keep track of two states: one progress of transitions within a word in $L'$ and also progress in $u$ we can use flags $1$ to signify when we're not inside $u$ and $2$ when inside. I don't understand why we need the union with $Q\times Q$. Why not a union with just $Q$ so it's a $3$-tuple, where the first two coordinates define that state from the beginning of the word and the third coordinate defines the state of $u$.

Transition function $\mu$ before reading $u$: $$ \mu((q,1),\sigma)=\{(\delta(q,\sigma),1), (q,q_0)\}\bigg| \sigma\in \sum, q\in Q $$

Either we read some letter before $u$ ($abc$ in my example) or we're at index $i$ (reading $k$ in my example in the case of $(q,q_0)$)

$\mu$ when reading $u$: $$ \mu((q,p), \epsilon)\supseteq\{(\delta(q,\sigma),\delta(p, \sigma))\}\bigg|\sigma \in \sum, q,p \in Q $$

2) We can't read $u$ directly from the input so we need $\epsilon$ to "connect" to $u$. Do we need $\delta(q,\sigma)$ to continue reading the original word ($def$ in my example) while $\delta(p, \sigma)$ is to start reading $u$ ($xyz$ in my example)?

reading the end of $u$: $$ \mu((q,p),\epsilon)\supseteq\{(q,2)\}\bigg| q\in Q, p\in F $$

3) Does this transition mean that we arrive to the end of $u$? So $(q,2)$ to signify the end of $u$?

continuation from reading $u$: $$ \mu((q,2),\sigma)=\{\delta(q,\sigma),2)\}\bigg|\sigma \in \sum, q\in Q $$

4) does this mean that we read the last letter of $u$ and eventually get to the last letter of the original word? It would be $def$ letters from my example. But why reading each of those letters would be an accepting state? Shouldn't reading only $f$ lead to the accepting state?


Your Answer

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

Browse other questions tagged or ask your own question.