# Is the complement of this context-free language also context-free?

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?

• See this related post: cs.stackexchange.com/questions/133797/… Commented Jun 17 at 17:13
• 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? Commented Jun 17 at 21:47

## Summary

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.