I just found out about uncountable and infinitary languages and I'm not sure what "string" means now. Originally, I had conceived of a string being, at most, a countable sequence of symbols with a least (leftmost) member. Since this fails to account for several types of infinite-length string (for example, strings that have no first or last symbol, uncountable strings), I'm at a loss as to what "string" means in the first place.

At the very least a string consists of a set [or class?] of symbols$^0$ with some kind of order, but I'm not sure where the line between "string" and "digraph" is drawn. If there are no restrictions, then the notion of "string" seems sufficiently general to be indistinguishable from "binary relation."


To give something of a starting point, I had originally thought to define a general "closure" operation that gives the set of all strings up to a certain (possibly infinite) length.

Let $\gamma$ be some fixed ordinal, then...


This readily generates the set of $\omega$-length strings when $\gamma=\omega+1$. However, the closure described above excludes strings which are not "well ordered." For example, strings with no leftmost symbol, which can be generated by infintary left-recursive grammars. Even extending the above to count reverse-order types for each ordinal$^1$ excludes the case of "cyclic" and "dense" strings (provided that such things are permitted).

$^0$ when referring to the characters of a string as a set [class?], assume that each character is identified with a pair $(k,s)$, where $s$ is the symbol and $k$ is a "tag" distinguishing different instances of $s$. If you take this one step further, then a string is a function from some set [class?] $X$ to a set $S$ of primitive symbols, plus a binary relation [order?] on $X$.

$^1$ $X^{\omega^*}$, appropriately defined, would account for $\omega$-length "left-recursive" strings

  • 1
    $\begingroup$ I imagine there are many definitions of string depending on context. $\endgroup$ – copper.hat Jan 28 at 19:12
  • $\begingroup$ @copper.hat The context is formal languages over arbitrary (possibly infinite) sets of primitive symbols. $\endgroup$ – R. Burton Jan 28 at 19:15
  • $\begingroup$ en.m.wikipedia.org/wiki/Alphabet_(formal_languages) $\endgroup$ – user645636 Jan 28 at 19:29
  • $\begingroup$ @RoddyMacPhee $\Sigma^\omega$ only covers the cases of countable strings with least (leftmost) member. $\endgroup$ – R. Burton Jan 28 at 21:54

I prefer to use the term word instead of string. Successive notions of words over an alphabet $A$ have been defined and studied: finite words, infinite words, bi-infinite words, words over ordinals and words over linear orderings. See [1] for a survey. Cyclic words were also considered: they are equivalence classes of cyclic permutations of finite words.

[1] Véronique Bruyère and Olivier Carton, Automata on linear orderings, J. Comput. System Sci. 73 (2007), no. 1, 1--24. (See also here).

| cite | improve this answer | |
  • $\begingroup$ Thank you, this is exactly what I was looking for! I noticed that the authors only mention countable words. Is it generally accepted that the length of a word must be countable? $\endgroup$ – R. Burton Jan 30 at 18:48
  • 2
    $\begingroup$ No, words over any linear order also have been studied, see A. Bès, and O. Carton, A Kleene theorem for languages of words indexed by linear orderings. Internat. J. Found. Comput. Sci. 17 (2006), no. 3, 519--541. $\endgroup$ – J.-E. Pin Jan 30 at 23:20

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.