Question from an old exam:

Consider the alphabet $A=\{a, b, c, 1, 2\}$ and two fixed words $u=aaab$ and $v=baac$. Let $\mathcal{G}$ be a context-free grammar with the rules $$ S \rightarrow \epsilon | uS1 | vS2 $$ Let $L$ be the language of this grammar. Is the complement $A^* \setminus L$ of the language $L$ a context-free language?

Writing a grammar seems tedious and non-obvious. I tried to find a counterexample but without success, e.g., $A^* \setminus L \cap u^*v^*2^*1^*$, which results in $u^i v^j 1^l 2^k$ such that $j \neq l$ and $i \neq k$, but the resulting set is obviously context-free.

At this point, I'm not sure what the answer to the above question is.
Could I ask for some guidance?

  • $\begingroup$ See this related post: cs.stackexchange.com/questions/133797/… $\endgroup$
    – codeR
    Commented Jun 17 at 17:13
  • 1
    $\begingroup$ For starters. How about the case where $u=b$ and $v=c$ instead? So $S\to \varepsilon \mid bS1\mid cS2$. Can you show that its complement is context-free? $\endgroup$ Commented Jun 17 at 21:47

2 Answers 2



The above context free grammar $\mathcal{G}$ has an equivalent pushdown automation $M$. As the starting letters of $u$ and $v$ are different ($a$ and $b$), we can create a $M$ which is a deterministic pushdown automation construction below). This means there exists a complement deterministic pushdown automation $M^C$ which accepts $A^* \setminus L$, and an equivalent context free grammar $\mathcal{G}^C$

Construction of $M$

I define $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ with:

  • states: $Q=\{q_0, q_\#, q_{u_1}, q_{u_2}, q_{u_3}, q_{u_4}, q_{v_1}, q_{v_2}, q_{v_3}, q_{v_4}, q_1, q_2, q_{p}, q_{d}\}$
  • input alphabet: $\Sigma = A =\{a,b,c,0,1\}$
  • stack alphabet: $\Gamma =\{\#, U, V\}$
  • start state: $q_{0}$
  • accepting states: $F=\{q_0, q_\#, q_p\}$

And the transition function $\delta: Q \times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow (Q \times \Gamma_\epsilon) \cup \{\emptyset\}$ has values:

  • $\delta(q_0, \epsilon, \epsilon) = (q_\#, \#)$
  • $\delta(q\in\{q_\#, q_{u_4}, q_{v_4}\}, a, \epsilon) = (q_{u_1}, U)$
  • $\delta(q\in\{q_\#, q_{u_4}, q_{v_4}\}, b, \epsilon) = (q_{v_1}, V)$
  • $\delta(q\in\{q_{u_1}, q_{u_2}, q_{u_3}, q_{v_1}, q_{v_2}, q_{v_3}\}, (\text{correct next letter in }u \text{ or }v), \epsilon) = (\text{next state}, \epsilon)$
  • $\delta(q\in\{q_{u_4}, q_{v_4}, q_1, q_2\}, 1, U) = (q_1, \epsilon)$
  • $\delta(q\in\{q_{u_4}, q_{v_4}, q_1, q_2\}, 2, V) = (q_2, \epsilon)$
  • $\delta(q\in\{q_1, q_2\}, \epsilon, \#) = (q_p, \epsilon)$

All the other $\delta$ values are filled to transfer illegal states to $q_{im}$ and to satisfy

For every $q \in Q$, $\sigma \in \Sigma$ and $\gamma \in \Gamma$, exactly one of the values $$\delta(q, \sigma, \gamma), \delta(q, \sigma, \epsilon), \delta(q, \epsilon, \gamma) \text{ and } \delta(q, \epsilon, \epsilon)$$ is not $\emptyset$.

Now to get $M^C$, we can just complement the accepting states in the above automata $F = Q \setminus \{q_0, q_{\#}, q_p\}$. We can do this because there is no accepting state in $M$ which goes to a non-accepting state without reading a letter from the input string.

We can also convert this PDA to a CFG using a cumbersome algo (linked below). I'm leaving that to the reader, but if you want an idea on how it might look like, I constructed the below (wrong) grammar before writing this answer

$$\begin{matrix} S &\rightarrow& a\,S \:|\: b\,S \:|\: c\,S \:|\: 1\,S \:|\: 2\,S \\ &|& S\,a \:|\: S\,b \:|\: S\,c \:|\: S\,1 \:|\: S\,2 \\ &|& T\,a \:|\: T\,b \:|\: T\,c \\ &|& a\,T \:|\: 1\,T \:|\: 2\,T \\ &|& bb\,T \:|\: cb\,T \:|\: 1b\,T \:|\: 2b\,T \\ &|& bab\,T \:|\: cab\,T \:|\: 1ab\,T \:|\: 2ab\,T \\ &|& baab\,T \:|\: caab\,T \:|\: 1aab\,T \:|\: 2aab\,T \\ &|& bc\,T \:|\: cc\,T \:|\: 1c\,T \:|\: 2c\,T \\ &|& bac\,T \:|\: cac\,T \:|\: 1ac\,T \:|\: 2ac\,T \\ &|& aaac\,T \:|\: caac\,T \:|\: 1aac\,T \:|\: 2aac\,T \\ &|& aaab\,T\,2 \:|\: baac\,T\, 1 \\ \\ T &\rightarrow& \epsilon \:|\: aaab\,T\,1 \:|\: baac\,T\,2 \end{matrix}$$

This grammar is wrong because it can accept $aaab1 \underbrace{\longrightarrow}_{S1} aaab \underbrace{\longrightarrow}_{Sb} aaa \underbrace{\longrightarrow}_{Sa} aa \underbrace{\longrightarrow}_{Sa} a \underbrace{\longrightarrow}_{Ta} \epsilon$ but the intended grammar might look something like this.

Reference for definitions and theorems: https://basics.sjtu.edu.cn/~longhuan/teaching/CS3313/chap2_DPDA.pdf

Reference for constructing CFG given PDA: https://www2.lawrence.edu/fast/GREGGJ/CMSC515/chapt02/Equivalent.html


Here's a somewhat simple, non-constructive approach.

Try to convince yourself, that $\mathcal{G}$ generates a deterministic context-free language. Since all deterministic context-free languages are closed under complement, it follows that $A^* \setminus L$ is also (deterministic) context-free.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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