3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Note that v is not necessarily in L, but it does have a finite number of letters (2) so I don't think that causes a problem. $\endgroup$ – Dash Oct 24 '12 at 5:09
  • 4
    $\begingroup$ your idea should work. $\endgroup$ – Ran G. Oct 24 '12 at 5:20
  • $\begingroup$ The only technical consideration I think is that you cancel the accept status of the the old DFA accept states. If you want to compress it down a little, you can add 3 states in a line, the last being the accept state, with all symbols on the two transitions, and epsilon transitions from the old accept states to the first state of this little linear fragment. $\endgroup$ – Luke Mathieson Oct 24 '12 at 6:01
6
$\begingroup$

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'=Q\cup\{q_\text{new1},q_\text{new2}\}$,
  • $F'=\{q_\text{new2}\}$,
  • ....

Then you should prove, using the acceptance criteria for $M$ and $M'$, that $w\in L(M) \iff wv\in L(M')$, for all $v\in \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.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ Add one letter, and apply the operation twice :) $\endgroup$ – Hendrik Jan Oct 24 '12 at 9:33
  • $\begingroup$ For the alternative, you'd need some uneven anchor as well. $\endgroup$ – Raphael♦ Oct 25 '12 at 10:55
  • $\begingroup$ Thank you, I went with the alternative approach as it was easier to argue formally! $\endgroup$ – Dash Oct 29 '12 at 5:26

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.