[Solved]: If $L$ is a regular language, how to prove $L_1 = { uv mid u in L, |v| =2 }$ is also regular?

ignougroup
Problem Detail: 

If $L$ is a regular language, prove that the language $L_1 = { uv mid u in L, |v| =2 }$ is also regular.

My idea: $L$ can be represented as a DFA and then you could add 2 consecutive transitions from every final state for the letters of $v$, creating a new NFA diagram. Is that correct? I’m not sure how to make this a formal proof.

Asked By : Dash

Answered By : A.Schulz

Your idea is correct. You should take the following path to formally write it up/prove it. First assume that $L$ is accepted by some DEA $M=(Q,Sigma,delta,q_0,F)$ then define a new NEA $M’=(Q’,Sigma,delta’,q’_0,F’)$ based on $M$. Just express you ideas formally, for example start with

  • $Q’=Qcup{q_text{new1},q_text{new2}}$,
  • $F’={q_text{new2}}$,
  • ….

Then you should prove, using the acceptance criteria for $M$ and $M’$, that $win L(M) iff wvin L(M’)$, for all $vin Sigma^2$. Alternative approach The following idea will also prove the statement but results in an easier proof. First show that the language of words with exactly two characters is regular, and then argue with the closure properties for regular languages.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6279