# Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

Let $$L$$ be a language over an alphabet $$\Sigma$$ and let

$$\text{MIN}(L) = \{ w \in L \mid \forall x,y \in \Sigma^* : (w = xy \land x \in L) \implies y = \varepsilon \}$$ $$\text{MAX}(L) = \{ w \in L \mid \forall x \in \Sigma^+ : wx \not\in L \}$$

Simply put, $$\text{MIN}(L)$$ consists of words from $$L$$ such that none of their proper prefixes is in $$L$$, and $$\text{MAX}(L)$$ consists of words from $$L$$ which are not a proper prefix of any word in $$L$$.

Now the question is: For given context-free grammar $$G$$, is it decidable whether language $$\text{MIN}(L(G))$$ is context-free or not, similarly with language $$\text{MAX}(L(G))$$ (of course we could define the problem with pushdown automaton instead of context-free grammar, or with any other finite description of context-free language). The problem is not trivial since the class of context-free languages is not closed under these operations:

$$\text{MIN}(\{ a^i b^j c^k \mid i, j, k > 0 \land (k \geq i \lor k \geq j) \}) = \{ a^i b^j c^k \mid i, j, k > 0 \land k = \min(i,j) \}$$

is not CFL, similarly

$$\text{MAX}(\{ a^i b^j c^k \mid i, j, k > 0 \land (k \leq i \lor k \leq j) \}) = \{ a^i b^j c^k \mid i, j, k > 0 \land k = \max(i,j) \}$$

is also not CFL (both can be shown using Ogden's lemma).

I would guess that the problem is undecidable, and I tried (somehow) proving it by contradiction with reduction of the undecidable Post correspondence problem, but got nowhere. Any ideas proving undecidability or creating an algorithm?

• I believe if $L(G)$ is a DCFL, then so is $\text{MIN}(L(G))$ (build a DPDA, and keep track of whether any prefix would have been accepted). This doesn't answer your question, of course.
– D.W.
Commented Apr 23 at 21:18
• Thank you for the advice, I'm relatively new here. Is it okay now? Commented Apr 24 at 12:06
• Looks great! Thank you! I appreciate your contribution, I hope to see you back on the site.
– D.W.
Commented Apr 24 at 16:16

Ok so I think I figured it myself at last.

In case of $$\text{MIN}$$ operation, for the sake of contradiction, let's assume it is decidable. Now let $$(X = (x_1,...,x_n), Y = (y_1,...,y_n))$$ be an instance of PKP over an alphabet $$\Sigma$$ such that $$\# \not\in \Sigma$$. We could construct CFG for language

$$L_{XY}^C = \{ x_{i_1} ... x_{i_k} \# i_k...i_1 \# j_1 ... j_l \# y_{j_l} ... y_{j_1} \mid i_1,...,i_k,j_1,...,j_l \in \{ 1,...,n \} \}^C$$

(I leave it for the reader to realize why this language is context-free) as well as CFG for language

$$L_{pal} = \{ w \in \Gamma^* \mid w = w^R \}$$

where $$\Gamma = \Sigma \cup \{ 1,...,n, \# \}$$. Now it should not be hard to see, that $$L_{XY} \cap L_{pal}$$ is empty language (and therefore CFL) iff the instance of PKP has no solution, and is not CFL iff the instance of PKP has a solution (because then it has infinitely many solutions and it can be simply shown using pumping lemma for context-free languages that it is not CFL).

Now WLOG assume that $${\\\} \not\in \Gamma$$. We will construct language

$$L = L_{pal} {\\\} L_{XY}^C {\\\} \cup L_{XY}^C {\\\}$$

Language $$L$$ is obviously also context-free, because CFLs are closed under concatenation and union. It's easy to see that the only words from $$L$$ that have also some proper prefix from $$L$$ are precisely words from $$L_{XY}^C {\\\} L_{XY}^C {\\\} \cap L$$. Therefore

$$\text{MIN}(L) = (L_{pal} {\\\} L_{XY}^C {\\\} \cup L_{XY}^C {\\\}) - L_{XY}^C {\\\} L_{XY}^C {\\\} = (L_{pal} - L_{XY}^C) {\\\} L_{XY}^C {\\\} \cup L_{XY}^C {\\\} = (L_{pal} \cap L_{XY}) {\\\} L_{XY}^C {\\\} \cup L_{XY}^C {\\\}$$

Finally, language $$\text{MIN}(L)$$ is CFL iff language $$L_{pal} \cap L_{XY}$$ is CFL, because of closure of CFLs under right quotient with regular languages (language $${\\\} \Gamma^* {\\\}$$), and also because of closure under concatenation and union. So if we could decide whether $$\text{MIN}(L)$$ is CFL or not, we could also decide if an instance of PKP has solution, which derives a contradiction.

In case of $$\text{MAX}$$, it can be also proved very similarly that the problem is undecidable - realize what is the result of $$\text{MAX} (L_{XY}^C {\\\} L_{pal} {\\\} \cup L_{pal} {\\\})$$ and utilize that CFLs are closed under intersection with regular languages.