Decidability of "Is this regular expression prefix-free?"

Question

Say that string $x$ is a prefix of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it doesn’t contain a proper prefix of any of its members. $$ \text{Prefix-FreeREX} = \{(R) \mid R \text{ is a regular expression and $L(R)$ is prefix-free}\} $$ I was wondering about how to prove that Prefix-FreeREX is decidable. Also why does a similar approach fail to show that Prefix-FreeCFG is decidable?

Answer 1

Let $L$ be a language on the alphabet $A$. Then $L$ is prefix-free if $L \cap LA^+$ is empty. If $L$ is regular and given by a regular expression, then $L \cap LA^+$ is also regular (and one can effectively compute a regular expression for it). Now testing whether a given regular language is empty is decidable.

For context-free languages, the situation is different. Above proof does not work because the context-free languages are not closed against intersection. In fact, there is no algorithm to decide whether a given context-free grammar generates a prefix-free language.

Here is a proof of this claim [Luc Boasson, personal communication].

Let $(u_1, v_1), \dotsm, (u_n,v_n)$ be two finite lists of words of $A^*$ defining an instance of the Post Correspondence Problem (PCP) and let $X = \{x_1, \ldots, x_n\}$ be an alphabet of $n$ letters. Assume that $A$ and $X$ are disjoint and consider the homomorphims $u, v: X^* \to A^*$ defined by $u(x_i) = u_i$ and $v(x_i) = v_i$. Consider the languages \begin{align} U &= \{x^Ru(x) \mid x \in X^+ \} \\ V &= \{x^Rv(x) \mid x \in X^+ \} \end{align} Let $\sharp$ be a new letter. Then $U \cup V\sharp$ is a context-free language. It is prefix-free if and only if $U$ and $V$ are disjoint if and only if the Post Correspondence Problem has no solution. Thus deciding whether a given context-free language is prefix-free is undecidable.

Answer 2

A deterministic finite automaton $A$ accepts a prefix-free language if and only if there is no accepting run which contains more than one final state. That, in turn, is the case if and only if $A$ has no final state that is reachable from a final state which, in turn, is reachable from the initial state. This can be checked by simple graph traversals.

So you can decide your problem by converting the regular expression to an equivalent automaton, determinising and then performing above mentioned checks.

Intuitively, this won't work for CFL (that is PDA) because

• there is a one-state PDA for every CFL, so there's little to see, and
• not every CFL has a deterministic PDA.