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

Question

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?

Answer 1

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

Answer 2

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.