[Math] Proper suffix, suffix and empty string

formal-languages

I found this definition on Wikipedia.

Suffix. A suffix of a string is any substring of the string which includes its last letter, including itself. A proper suffix of a string is not equal to the string itself.

Is the empty string a suffix of itself?

if I have a language formed from f Σ = {a, b}, with a Kleene star.
How many elements from Σ* can we form such that no two elements are a proper suffix of each other?

Edit:
is there a way to know how many Language of at most 2 letter strings formed from {a, b} where neither strings is a proper string of the other. Know the number without having to list all of them.

Best Answer

I disagree with the definition given on Wikipedia. A word $s$ is a suffix of a word $w$ if there exists a word $u$ such that $w = us$. In particular, $s$ can be the empty word and the empty word is a suffix of itself.

For the second question, infinitely many. Just take the suffix code $ba^*$: $ba^i$ is a suffix of $ba^j$ if and only if $i = j$.

EDIT 1. I have now edited the substring entry on Wikipedia.

EDIT 2. Up to taking the reversals of the words, your new question is asking for the number of sets $T \subset \{a,b\}^{\leqslant 2}$ such that no word of $T$ is a prefix of another word of $T$. Such a set is represented by a binary tree of depth $\leqslant 3$. Now this detailed answer by Brian M. Scott tells you that the number $b_n$ of binary trees of height $\leqslant n$ satisfies $b_{-1} = 1$, $b_0 = 2$ and $b_{n+1}=b_n^2+1$. Thus $b_1= 5$ and $b_2 = 26$. Thus the answer to your question is $26$. See also OEIS A$003095$.

Related Question