$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$

Here is my attempt solution, but it is not completely correct, any hint is appreciated (not sure how I can ensure that $u$ and $v$ to have the same number of 1).

\begin{align} S &\rightarrow S_l \mid S \mid S_r\\ S_l &\rightarrow 0S_l \mid 1S_l \mid S_l0 \mid S_l1 \mid \varepsilon \\ S_r &\rightarrow 1S_r \mid 2S_r \mid S_r1 \mid S_r2 \mid \varepsilon \end{align}

  • $\begingroup$ Why do you think your grammar is correct? Have you tried proving it correct or tested by verifying that words up to length, say, 5 are covered correctly? Also, what do you expect here? There is no question. $\endgroup$ – Raphael Jun 11 '18 at 9:27

The idea is to extract a pair of 1s one by one, so the key grammar is

\begin{align} S&\rightarrow S_01S1S_2 \\ S&\rightarrow S_0S_2 \end{align}

where $S_0$ represents $0^*$ and $S_2$ represents $2^*$.


This answer refers to the question as originally stated, in which $L$ is defined as follows: $$ L = \{uv \in \{0,1,2\}^* \mid u,v \in \{0,1\}^*, \text{and $u$ has the same number of $1$s as $v$}\}. $$

Your language is regular, since it consists of all words over $\{0,1\}$ with an even number of $1$s.

  • $\begingroup$ Sorry, it is my bad that I changed the meaning carelessly in the first edit. The current question is what OP wants. $\endgroup$ – xskxzr Jun 11 '18 at 11:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.