HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is the meaning of a prefix-free language?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
meaningthewhatfreelanguageprefix

Problem

Tried a bunch of resources to read about it, still don't really get it.

This is what Wikipedia says


A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system.

This is my understanding so far:
I have a language L that has all these words L = {"a", "b"}. From my understanding, right now my language L is prefix free, but if I add a new word to it like "ac", so that my language becomes L = {"a", "b", "ac"}, its not prefix-free anymore?

Is my thinking correct? or am I missing anything?

Solution

You are correct: {a, b} is prefix-free, but {a, b, ac} is not.

The idea of a prefix-free code is that once you recognize a word you know for sure it's a word. So for instance a code that includes both CONNECT and CONNECTICUT is not prefix-free, because if you start parsing a phrase like

ACONNECTICUTYANKEEINKINGARTHURSCOURT


taking every word as soon as you see it you're going to read this as

A, CONNECT, I, CUT, YANK, (error)


since you can't do anything with the string EEINKINGARTHURSCOURT. (That's assuming you don't also consider CON a word also; if so, things would be even worse.)

Note that adding spaces between words is basically a way of making a code prefix-free: if "connect" by itself isn't considered a word, but "connect " is, then you'll have no trouble parsing

A CONNECTICUT YANKEE IN KING ARTHURS COURT

Code Snippets

ACONNECTICUTYANKEEINKINGARTHURSCOURT
A, CONNECT, I, CUT, YANK, (error)
A CONNECTICUT YANKEE IN KING ARTHURS COURT

Context

StackExchange Computer Science Q#84777, answer score: 7

Revisions (0)

No revisions yet.