I've got a simple question:

Let's say we have the following definition of a language over some alphabet: $L = \{w \mid w \text{ contains the infix } aab\}$

Does that mean $aab \in L$? or does "$aab$" have to be "wrapped" on both sides by other letters?


Yes, if $A$ is the alphabet, then $L = A^*aabA^*$.

Now, what about terminology? Lothaire in the first chapter of his book Combinatorics on words gives the following definitions. A word $v \in A^*$ is said to be a factor of a word $x \in A^*$ if there exist words $u, w \in A^*$ such that $x = uvw$. A factor is proper if $v \not= x$.

In my opinion, the word infix is also perfectly fine, since it gives a natural counterpart to prefix and suffix. Terms involving "sub" like subword and substring are also frequently used in the literature. I personally prefer to follow Lothaire and say that a word $v \in A^*$ is a subword of a word $x \in A^*$ if $v = a_1a_2 \cdots a_n$ (where $a_i \in A$ and $n \geqslant 0$) and there exist $y_0, ..., y_n \in A^*$ such that $x = y_0a_1y_1a_2 \cdots a_ny_n$. This definition makes the term subword a synonym of subsequence, which I find quite natural.

Anyway, with so many different terminology around, it is not a bad idea to remind the reader of precise definitions if there is any risk of ambiguity...

  • $\begingroup$ Thank you. I'll have to ask my teacher for his exact meaning. $\endgroup$ – Paz Feb 22 '14 at 11:55
  • $\begingroup$ The word infix seemd used more often to qualify a string representation of operator-operand tree (aka terms of a free algebra). Prefix (resp. suffix) notation places the operand before (resp. after) its arguments. Infix notation places the operator between arguments, which may raise ambiguity problems, addressed in various ways. $\endgroup$ – babou Feb 22 '14 at 17:12

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.