7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Apr 23 at 21:18
  • $\begingroup$ Thank you for the advice, I'm relatively new here. Is it okay now? $\endgroup$
    – JimmyB
    Commented Apr 24 at 12:06
  • $\begingroup$ Looks great! Thank you! I appreciate your contribution, I hope to see you back on the site. $\endgroup$
    – D.W.
    Commented Apr 24 at 16:16

1 Answer 1

2
+100
$\begingroup$

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.

$\endgroup$

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.