snippetMinor
If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular?
Viewed 0 times
l_1midregularlanguagealsoprovehow
Problem
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.
$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.
Solution
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
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.
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.
Context
StackExchange Computer Science Q#6279, answer score: 6
Revisions (0)
No revisions yet.