1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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}$

| cite | 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.