0
$\begingroup$

I can't find out how to find a context free grammar for bellow language, is there any specific way to solve that?

$L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$

$\endgroup$
1
$\begingroup$

$\Sigma = \{a,b,c\}$. Consider the two cases:

  1. $n_c(w) > n_a(w) + n_b(w)$: The idea is to create one more $c$ for each $a$ or $b$ produce in the word: \begin{align} S_c \rightarrow aS_cS_c | bS_cS_c | cS_c | c \end{align}
  2. $n_c(w) < n_a(w) + n_b(w)$: In this case, we can produce as many $c$'s as $a$ and $b$ combined + 1. \begin{align} S_{ab} \rightarrow aS_{ab} | bS_{ab} | cS_{ab}S_{ab}|a|b \end{align}

The grammar for the required language would be : $S \rightarrow S_c | S_{ab}$.

$\endgroup$
2
  • 1
    $\begingroup$ How produce $cca$? I think you should write \begin{align} S_c \rightarrow aS_cS_c | bS_cS_c |cS_c| c \end{align} $\endgroup$
    – nima
    Oct 31 '21 at 8:01
  • $\begingroup$ @nima Thanks, I updated my answer. $\endgroup$
    – prime_hit
    Nov 2 '21 at 16:14

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.