Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property?

The definition says that language has prefix/suffix property requires that there is no code word in the system that is a prefix (initial segment) of any other code word in the system.

So if we have this finite language with $\varepsilon$ this mean that, there arent any prefix/suffix of empty word so our language has or not prefix/suffix property?


You probably mean $L=\{\varepsilon\}$, i.e. the language which contains only the empty word, as opposed to the empty language. Both the empty language and the language which contains only the empty word have the prefix/suffix property, since they satisfy the definion.

However, the prefix property is a property of a code, not a property of a language. A language can describe a code, but neither the empty language nor the language which contains only the empty word describe a code. So in the end it is irrelevant whether those languages have the prefix/suffix property.

Edit rici is right that Hopcroft&Ullman say that the LR(0) grammars define exactly the DCFL's having the prefix property. (They hasten to add that the prefix property is not a severe restriction.) So in this case it is good that the empty language and the language which contains only the empty word have the prefix property. Additionally, Berstel&Perrin allow the empty set as a code, so you can also dispute my other claim. But they agree that $\{\varepsilon\}$ has the prefix property, and is not a code:

Proposition 2.1.9 Any prefix (suffix, bifix) set of words $X\neq \{\varepsilon\}$ is a code.

Both Hopcroft&Ullman and Berstel&Perrin consider $\varepsilon$ to be a prefix/suffix of any word, but they require a proper prefix/suffix in the definition of the prefix/suffix property. (This is clearly the right thing to do, otherwise no set of words would have the prefix/suffix property.)

  • $\begingroup$ The "prefix property" is a property of a set of strings. Where the set comes from is more or less irrelevant to the definition; the set could be the set of codings, as you suggest, but it could just as well be the set of strings derived by a grammar. A language is nothing other than a set of strings. So it is perfectly reasonable to say that a language has the prefix property. You'll find such a definition in Hopcroft&Ullman, for example. $\endgroup$ – rici Feb 4 at 2:22
  • $\begingroup$ I couldn't find a clickable link for page 254 in Hopcroft&Ullman but here's an example from a different textbook: books.google.com.pe/… $\endgroup$ – rici Feb 4 at 2:30

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.