CSC B36: proving closure property using FSA method

Introduction

Suppose we have a language operation, f(L), which takes a language and transforms it into another language. Suppose further that we want to prove that our operation f preserves regular languages -- i.e., whenever L is a regular language, so is f(L). One way to prove this property is to use the regex method -- more precisely, structural induction (on structure of regexes).
Another way to do this is to use FSAs.

FSA method

Starting with a regular language L, the BIG RESULT tells us that there is a DFSA M that accepts L. We would get our desired result if we can show how to take an arbitrary DFSA M and construct another FSA M' (it can be DFSA or NFSA) such that L(M')=f(L(M)) -- i.e, that M' accepts f(L(M)).

For this course, here are the questions you must answer -- in clear English sentences, not diagrams -- in order to describe the construction of M'.

How many copies of M are needed in M'?
What additional states (if any) are needed?
What is the initial state of M'?
What are the accepting states of M'?
What transitions need to be added/removed/changed?
- For each transition, make it clear what symbol (or epsilon) is being read.
- For each transition, make it clear what state it goes from and what state it goes to.

You may provide diagrams if they help to clarify the description of your construction, but just having diagrams is considered inadequate.

Example

Consider the language operation Ins0 from the additional notes on "structural induction for regular expressions".

Sigma = {0,1}.
f(L) = {y: for some u,v in Sigma*, uv in L and y = u0v}.

Here is the description of how to construct M' given a DFSA M.

Take 2 copies of M. Call them M1 and M2.
No additional states are needed. <<< optional when "no additional state"
The intitial state of M' is the initial state of M1.
The accepting states of M' are the accepting states of M2.
For each state q in M1, add a 0-transition from q in M1 to the corresponding q in M2.
- For a DFSA M with n states, we would add n transitions.
- Since the original 0-transitions are not deleted, the addition of these transitions makes M' nondeterministic.

You should be able to draw an appropriate diagram from just reading this description.