patternModerate
What is the origin of λ for empty string?
Viewed 0 times
thewhatemptyforstringorigin
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#64819, answer score: 12
Revisions (0)
No revisions yet.