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.

Improve this question
$\endgroup$
3
  • $\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, 2012 at 5:09
  • 4
    $\begingroup$ your idea should work. $\endgroup$
    – Ran G.
    Oct 24, 2012 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, 2012 at 6:01

2 Answers 2

Reset to default
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.

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

If $A$ is the alphabet, $L_1 = LAA$. Now $A$ is finite and thus regular. Thus if $L$ is regular, then $L_1$ is the product of three regular languages and hence is regular.

Exercise. Use the same type of argument to show that if $L$ is context-free, then so is $L_1$.

Improve this answer
$\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.