2
$\begingroup$

Create a context free grammar for L. $$ L=\{a^nb^mc^k | n+m \neq k\} $$

First I tried to create a CNF for a language that accepts strings in which $n+m = k$. I got this:

$$ S \rightarrow aAc $$ $$ A \rightarrow aAc \mid B $$ $$ B \rightarrow bBc \mid \epsilon $$ to create a CNF for $L$, I wanted to add a new start state that basically adds another symbol to the strings accepted by the CNF above. I can add as and cs with no problem but don't know how to add bs since b is in the middle.

$\endgroup$
2
  • 5
    $\begingroup$ You're very close — I suggest spending more time on the problem. $\endgroup$ Apr 19, 2022 at 17:36
  • 1
    $\begingroup$ Hint: to add b's, you just need to change the last production slightly (and add other non-terminal symbols accordingly) $\endgroup$
    – justhalf
    Apr 20, 2022 at 8:10

2 Answers 2

6
$\begingroup$

I would like to add that the language $L_0=\{a^n b^m c^k\;|\;n+m=k\}$ is the deterministic context-free language, and a DPDA can be constructed recognizing $L_0$ by the final state. Then we can use the closure property of DCFLs under the complement and obtain a DPDA for $L$ swapping the final and non-final states in the initial DPDA (with a little mess with the trap state).

The main construction is rather straightforward, but it is refined in the two following aspects:

  1. The new stack symbol $A$ is introduced, marking the very first occurrence of either $a$ or (if $a$ block is empty) $b$. If we use the single stack symbol $B$, then we would also have a DPDA (having an $\epsilon$-transition to the state $Q_4$ by the stack symbol $Z_0$), but that DPDA is not so convenient to construct a complement, since it contains $\varepsilon$-transitions between the final and the non-final state. The DPDA below has no such transitions, distinguishing the last pop operation.
  2. We omitted most transitions to the trap state $T$, because these transitions correspond to the words not belonging to the language $a^* b^* c^*$ (and the initial language $L$ is a subset of this regular language, thus these transitions kick from $L$ as well).

Now simply swap the final and non-final states and get the DPDA for the required language. If you like to construct PDAs, this technique works rather well for recognizing complements of the deterministic languages, but since you ask not for a PDA, but for a CFG, you still have to make the PDA$\rightarrow$CFG transition. In the case considered, it is again quite straightforward (and gives almost the same result as the direct CFG construction): all what you need is to consider the stored $A$ and $B$ stack symbols as the nonterminals which derive a single letter $c$ if popped and $\varepsilon$ otherwise.

Btw, the PDAs above allow $n$, $m$, and $k$ to be zeros.

$\endgroup$
4
$\begingroup$

There's no procedure for creating a context-free grammar for the complement of a context-free language, because the complement of a context-free language might not be context-free, and the question of whether a language is context-free is not decidable.

Of course, particular context-free languages (and some languages which are not context-free) do have context-free complements, and this is an example of such a language. Indeed, as @Tonita observes in her excellent answer, $L^C$ is a deterministic context-free grammar, which are closed under complement. So that's not entirely a dead end.

But on the whole, it's rarely helpful to try to start with a grammar for $L$ and transform that into a grammar for $L^C$, since the latter might not even exist, and even if it dies, mechanically generating it could be a lot of work.

Here's another approach which often works for problems like this. When trying to deal with languages whose descriptions involve inequalities, it's often useful to remember that $i\ne j$ is the union of the two predicates $i<j$ and $i>j$, and furthermore that $i>j$ is the same as $\exists k>0 \mid i = j + k$. Finally, $a^{j+k} = a^ja^k$. That should be enough to quickly find the solution.

$\endgroup$
5
  • 5
    $\begingroup$ Re. “there's no procedure”: this is an informal reason, but as a formal argument it's missing some key parts. It could be the case that context-freeness is decidable on languages that are the complement of a context-free language. There could be a procedure that is guaranteed to produce a CFG if the language is context-free, but might not terminate otherwise. Do you happen to know if those are known to be false? $\endgroup$ Apr 20, 2022 at 8:30
  • $\begingroup$ @Gilles'SO-stopbeingevil' That is a good question. You can ask it as a new question here on cs.se. $\endgroup$ Apr 20, 2022 at 8:44
  • $\begingroup$ @gilles: you misunderstand my intent. I'm not trying to demonstrate whether $L$ is or is not context-free; it's a given that it is. Anyway, the absence of a closure property proves nothing. All my answer is trying to do is to guide OP in a direction which is often useful for finding CFGs for languages which contain inequalities. As Tonita points out, since $L^C$ is deterministic, there is in fact a procedure. All the sane, I think my way is easier. As for your question about recursive enumeration, that doesn't work in the general case because... $\endgroup$
    – rici
    Apr 20, 2022 at 16:11
  • $\begingroup$ ... it's also not decidable in general whether a CFG produces a particular language. (It's decidable in specific cases; for example, if the language is finite.) Again, that's an informal statement, but you can find the proof in any introduction to formal language theory. $\endgroup$
    – rici
    Apr 20, 2022 at 16:14
  • $\begingroup$ But even if it did work, it doesn't seem like the sort of procedure which would be advisable if you ran into this question on an exam :-) $\endgroup$
    – rici
    Apr 20, 2022 at 16:41

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.