15
$\begingroup$

I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$.

I think $\varepsilon$ is derived from the word "Empty". However I don't know what's the origin of $\lambda$.

In automata theory, there is the epsilon transition of automata, and it's also said to be the lambda transition. For example, JFLAP software uses $\lambda$ for the label of epsilon transitions by default.

I googled on the origin and searched cs.stackexchange, but I couldn't find. Does anyone know a reference that describes this?

Improve this question
$\endgroup$
11
$\begingroup$

The German Wikipedia claims that $\lambda$ comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics.

Chomsky used $I$ as the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use $1$ as the empty string, with the same justification.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ 1 is particularly nice when you're defining Regular Expressions algebraically. 1 is the empty string, 0 is the empty language, concatenation is $\cdot$ and union is $+$, and you get a Semi-ring. $*$ makes things a bit more complicated though. $\endgroup$
    – jmite
    Oct 19 '16 at 18:21
  • $\begingroup$ Thank you for the answer! It seems to be plausible, so I'm searching for the reference. Since the article of Formal Language of Wikipedia says the origin of FL is Gottlob Frege's Begriffsschrift (1879), I read the translated version of it today, but it doesn't seem to use the λ notation. Another historical paper Recursive Unsolvability of a Problem of Thue by Emil Post (1947) doesn't, either. Therefore I keep searching. Anyway, thanks for the big help :) $\endgroup$
    – nekketsuuu
    Oct 20 '16 at 11:13
8
$\begingroup$

Probably the notation originates from the "Finnish school".

My copy of 'Formal Languages' by Arto Salomaa (Academic Press, ACM monograph series, 1973) uses $\lambda$ for the empty string. And so does his 1969 book 'Theory of Automata' (Pergamon Press).

We move back. The classic 'Finite Automata and Their Decision Problems' by M.O. Rabin and D.Scott (April 1959) have the notation (capital) $\Lambda$ for "the empty tape with no symbols" (where a tape is a finite sequence of symbols).

One of the early people to write on finite automata was Trakhtenbrot and he used a symbol much like $\Lambda$ but typeset as $\land$ (as in his book with Barzdin, 1970, my russian is lousy but I recognize $\land p= p\land=p$).

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ IIRC, in Principia Mathematica (around 1910), Russell used $\Lambda$ for the empty set. I have no idea if this is somehow related. $\endgroup$
    – chi
    Oct 20 '16 at 14:21
  • $\begingroup$ @chi The books of Knuth are using $\Lambda$ for the nil-pointer. There must be a history of having $\Lambda$ mean "nothing". Might be related with the other answer where it is suggested that it stands for "Leer" or empty in German. $\endgroup$
    – Hendrik Jan
    Oct 28 '16 at 23:15

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.