Proving Closure Property using FSA

For a given Language Operation $f$, and a given Regular Language $L$, We can prove $f(L)$ preserves the regular language with a FSA.

Proving Process

1. The Big Result tells us there is a DFSA that accepts regular language $L$
2. We show that from taking an arbitrary DFSA $M$, we can construct another FSA $M^{\prime }$ s.t $L(M^{\prime })=f(L(M))$
3. We describe the construction of $M^{\prime }$ by noting:
   1. How many copies of $M$ are needed in $M^{\prime }$
   2. How many additional states are needed
   3. What is the initial state of $M^{\prime }$
   4. What are the Accepting State of $M^{\prime }$
   5. What transitions need to be added/removed/changed?

Example

Consider:

• $\Sigma =\{0,1\}$
• $f(L)=\{y:\text{ for some }u,v\in {\Sigma }^{\ast },uv\in L\wedge y=u0v\}$ A description to construct $M^{\prime }$ given a DFSA $M$:
• Take 2 copies of $M$, call them $M_1$, $M_2$
• No additional states are needed
• Initial state of $M^{\prime }$ is the same initial state of $M_1$
• The Accepting State of $M^{\prime }$ is the accepting state of $M_2$
• For each state $q$ in $M_1$, add a 0-transition from $q$ in $M_1$ to the corresponding $q$ in $M_2$
  • For DFSA with $n$ states, we would add $n$ transitions
  • Since the original $0$-transitions are not deleted, we are still a DFSA We should also be able to draw a diagram from this description.