0
$\begingroup$

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?

$\endgroup$

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.