7
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I think under your definition virtually no languages are prefix-free. It's a trivial solution, but the empty string x = "" is a prefix of all strings y; its associated z is equal to y. It's even a proper prefix, since the empty string x is not equal to y... unless y is also an empty string. So the only language that would be prefix-free is {""}, an empty string and nothing else. Did you mean to specify that x must be non-empty? Or maybe that, to be a proper prefix, neither x nor z can equal y? $\endgroup$ – Kevin J. Chase Apr 10 '15 at 14:42
  • $\begingroup$ @KevinJ.Chase Plenty of languages do not include the empty string. $\endgroup$ – Daniel Wagner Apr 10 '15 at 16:51
  • $\begingroup$ @DanielWagner: I see my mistake... I think I was correct that x = "" is a (trivial and annoying) proper prefix to any non-empty y, so if a language contained even one non-empty y along with the empty string, it would instantly fail to be prefix-free. But, as you say, plenty of regular languages don't contain the empty string. (I must have been thinking of the empty set, not string.) Finding a proper prefix that's not in the language might be clever or something, but it doesn't actually count... so good catch. $\endgroup$ – Kevin J. Chase Apr 11 '15 at 4:12
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think this proof is wrong: consider $X=\{7\}$ with $v(7)=89$ and $u(7)=8$. Clearly, there's no PCP solution, but both $789\#$ and its prefix $78$ are in the CFL. $\endgroup$ – xdavidliu Oct 11 '20 at 23:39
  • $\begingroup$ The issue in my comment above (and thus this proof) can be fixed by using two endmarkers instead of one: i.e. $U \% \cup V \% \#$. Only with two endmarkers is it valid to say that the CFL is prefix-free if and only if $U$ and $V$ are disjoint. $\endgroup$ – xdavidliu Oct 12 '20 at 1:41
7
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ what do you mean by "There's a one-state PDA for every CFL"? Surely there are CFLs that require more than one state to describe? Also, why does this graph traversal method require determinism? It seems like as long as one accept state is reachable from another, then it is not prefix free, and this is true regardless of whether deterministic or not? $\endgroup$ – xdavidliu Sep 16 '20 at 12:12
  • $\begingroup$ @xdavidliu 1) Nope. The standard triplet construction used to prove that CFG and NPDA describe the same set of languages always yields a single-state automaton. (If you terminate with empty stack; otherwise you'd need an additional final state, for a total of two.) $\endgroup$ – Raphael Sep 16 '20 at 15:48
  • $\begingroup$ 2) It breaks down in both directions. An NFA for a prefix-free language may have runs with multiple final states: if they are connected only by $\varepsilon$-transitions, no harm done. (In some texts, NFA are defined without $\varepsilon$-transitions; this argument doesn't work, then. There may be another.) Conversely, it's rather easy to come up with an NFA for a non-prefix-free language -- say, e.g., $\{a, aa\}$ -- for which no accepting run visits more than one final state. Roughly speaking, you need determinism to ensure that a prefix in the input implies a prefix in the (accepting) run. $\endgroup$ – Raphael Sep 16 '20 at 15:53
  • $\begingroup$ Good question, though, I had to think carefully to remember why I needed determinism! I might edit the answer alter. $\endgroup$ – Raphael Sep 16 '20 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.