# Prove the following language is regular?

Assume $$L_1$$ is a regular language, and define:

$$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$

Show that $$L$$ is regular.

I first tried to prove by showing that the pumping lemma holds true, then learned that it was not a double implication and can only be used to prove languages are not regular.

Then I tried to draw an NFA, but didn't make any progress.

What's a good way to prove that a language like this is regular?

The answer depends on whether $$L_1$$ is a language over $$\{a,b\}$$ or over $$\{a,b,c\}$$.

$$L_1$$ is a language over $$\{a,b\}$$

In this case, the easiest way to proceed is using closure operations. Show first (by constructing a DFA) that the following language is regular: $$L_2 = \{wcv \mid |w|_a+2|v|_b \equiv 3 \bmod 5 , w,v \in \{a,b\}^*\}.$$ Your language is $$L = L_1cL_1 \cap L_2$$.

$$L_1$$ is a language over $$\{a,b,c\}$$

In this case we have to be more careful. Given a DFA (or an NFA) for $$L_1$$, we construct one for $$L$$ which in three stages:

1. Simulate $$L_1$$ and keep track of the number of $$a$$s modulo 5. Whenever at an accepting state of $$L_1$$, add a nondeterministic move to stage 2.
2. Read $$c$$.
3. Simulate $$L_1$$ (starting from its initial state again) and keep track of the number of $$b$$s modulo 5. A state is accepting if it is accepting for $$L_1$$ and the constraint $$|w|_a+2|v|_b$$ is satisfied, where $$w$$ is the word read at the first stage, and $$v$$ is the word read at the third stage.

I'll let you fill in the details.

For every $$i=0,\dots,4$$, there exists a regular expression $$W_i$$ for the language of all words $$w$$ such that $$|w|_a \bmod 5 = i$$.

For example: $$((b+c)^*a)^i ( ((b+c)^*a)^5)^*(b+c)^*$$

Similarly, for every $$j=0,\dots,4$$, there exists a regular expression $$Z_j$$ for the language of all words $$z$$ such that $$2|z|_b \bmod 5 = j$$.

Then a regular expression for your language is $$\sum_{i=0}^4 W_i c Z_{(3-i) \bmod 5}$$