Prefix of a string

string theory prefix computation-theory
Caroline picture Caroline · Jan 22, 2016 · Viewed 14.4k times · Source

X is a prefix of a string y if there exists xz = y and x is a proper prefix if x is not equal to y.

Just wanted to make sure I understand the concept correctly.

For example, if there is a string y = "abracadabra" does it mean that there are loads of possible prefixes? So, if x is a prefix then x can be equal to "a", "ab", "abr" or even to "abracadabra" but in this case, when x=y, it is now called a not proper prefix as far as I understand. However, I am not really sure about the last part where x=y can it still be considered to be a prefix?

A language is prefix-free if no member is a proper-prefix of another member.

Again, not sure whether I understand it correctly. If, for example, there is a language = "Hello, World! My name is Andrew" , I think, it is prefix-free since the beginnings of each member are different from each other. However, in case if we have "Hello, World! How are you?" this language is not prefix-free anymore because "H" is a prefix of both "Hello" and "How". Is my way of thinking correct or have I misunderstood something?

No examples given in the book I am reading and it seems to be an easy topic so I guess that might be the reason why I can't find more detailed explanations. But I just, anyway, want to make sure I do not misunderstand anything.

I would be grateful for all the answers. Thank you.

Answer

Pachelbel picture Pachelbel · Jan 24, 2016

Yes, "abracadabra" is a prefix of "abracadabra", but not a proper one - "a", "ab", "abr", ..., "abracadabr" are the proper prefixes of "abracadabra". Your example for a language is a little bit confusing. Normally, a language is defined as a set of words / strings, but you are giving just one large string as a language example.

So, a language might be the set L1 = {"a", "b", "ab"}. However, this language is not prefix-free, since "a" is in L1 and is a proper prefix of "ab", which is also in L1.

The language L2 = {"abra", "cada", "bra"} is an example of a prefix-free language according to the definition you have given: "abra" is not a prefix of "cada" or "bra", "cada" is not a prefix of "abra" or "bra", and "bra" is not a prefix of "abra" or "cada".

Related questions

How to check whether a string contains a substring in JavaScript?

Usually I would expect a String.contains() method, but there doesn't seem to be one. What is a reasonable way to check for this?

Read More
How do I convert a String to an int in Java?

How can I convert a String to an int in Java? My String contains only numbers, and I want to return the number it represents. For example, given the string "1234" the result should be the number 1234.

Read More
How do I check if a string contains a specific word?

Consider: $a = 'How are you?'; if ($a contains 'are') echo 'true'; Suppose I have the code above, what is the correct way to write the statement if ($a contains 'are')?

Read More