1
$\begingroup$

let $L\subseteq\Sigma^*$ be a regular language.

for $\sigma \in \Sigma$ prove that $L'=\{w_1\sigma w_2:w_1w_2\in L\}$ is a regular languge.

I tried induction on the length of the regular expression of L.

there are 3 cases in the induction:

$r=r_1\cup r_2, r =r_1\cdot r_2 , r=(r_1)^*$.

the first one is pretty easy but now I stuck on the 2nd and the 3rd.

in the 2nd case:

$w_1\sigma w_2\in L' \leftrightarrow w_1w_2\in L=L(r)=L(r_1\cdot r_2 )=L(r_1)\cdot L(r_2 )$

but at this point I stuck cause I can't say that $w_1\in L(r_1)$ or something like that.

in the 3rd case:

$w_1\sigma w_2\in L' \leftrightarrow w_1w_2\in L=L(r)=L((r_1)^*)=L(r_1)^* \leftrightarrow w_1 w_2=\epsilon$ or $w_1w_2=w_1\cdot w_2...w_k, k>0, \forall i =1...k, w_i \in L(r_1)$

and I have no idea how to finish that case.

$\endgroup$
  • $\begingroup$ Can you create a finite state machine for $L^\prime$? You already know you can create a FSM for $L$, and you can use that as a starting point. $\endgroup$ – Larry B. Nov 1 '18 at 17:01
  • $\begingroup$ @FabioSomenzi any clue? $\endgroup$ – UltimateMath Nov 1 '18 at 18:52
  • $\begingroup$ Sorry for the misleading comment. I misread the definition of $L'$. I put a comma between $w_1$ and $w_2$, which made the problem trivial to solve with regular expressions. The actual problem is better tackled with automata as suggested by Larry B.. $\endgroup$ – Fabio Somenzi Nov 1 '18 at 22:07
1
$\begingroup$

The problem can be solved using automata, but your suggested approach is very interesting. However, you have to be very careful since there is nothing like "the regular expression of $L$" (a regular language admits infinitely many regular expressions that represent it). To avoid this potential problem, you can argue directly on regular languages as follows.

Let $a$ be a fixed letter of the alphabet $A$. For each language $L$ of $A^*$, let $$ L' = \{uav \mid u,v \in A^*,\ uv \in L\} $$ Let $\mathcal{C}$ be the class of all regular languages $L$ of $A^*$ such that $L'$ is regular. Our aim is to show that $\mathcal{C}$ contains all regular languages.

Step 1. The class $\mathcal{C}$ contains the empty language, the language $\{1\}$ and the languages $\{b\}$ for each letter $b$. Trivial (actually you could say directly that any finite language belongs to $\mathcal{C}$).

Step 2. The class $\mathcal{C}$ is closed under finite union. This follows from the formula $(L_1 \cup L_2)' = L_1' \cup L_2'$, which you already observed.

Step 3. The class $\mathcal{C}$ is closed under product. This follows from the formula $(L_1L_2)' = L_1L_2' \cup L_1'L_2$, which essentially says that if you want to insert an $a$ in $L_1L_2$, you have to insert it either in a word of $L_1$ or in a word of $L_2$.

Step 4. The class $\mathcal{C}$ is closed under star. This follows from the formula $(L^*)' = L^*L'L^* \cup \{a\}$ that I let you verify.

Thus $\mathcal{C}$ contains the finite languages and is closed under union, product and star: thus it contains all regular languages.

$\endgroup$

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.