Jakie jest pochodzenie λ dla pustego łańcucha?


14

Zazwyczaj używam symbolu dla pustego łańcucha (pusty wyraz lub łańcuch pusty). Ale wiem, że niektórzy ludzie używają λ zamiast ε .ελε

Myślę, że pochodzi od słowa „pusty”. Jednak nie wiem, skąd się bierze λ .ελ

W teorii automatów istnieje przejście epsilon na automatach, a także mówi się, że jest to przejście lambda. Na przykład oprogramowanie JFLAP domyślnie używa do oznaczania przejść epsilon.λ

Poszukałem źródła i szukałem cs.stackexchange, ale nie mogłem znaleźć. Czy ktoś zna referencję, która to opisuje?

Odpowiedzi:


10

W Niemiecka Wikipedia twierdzi, że pochodzi od „Leer”, co oznacza „puste” w języku niemieckim. Wydaje się to prawdopodobne, ponieważ niemiecki był jednym z głównych języków matematyki.λ

W swoich wczesnych pracach Chomsky używał jako pustego łańcucha (a właściwie jako elementu tożsamości dla łączenia łańcuchów). Niektóre osoby w kombinatorykach nadal używają 1 jako pustego ciągu, z tym samym uzasadnieniem.I1


2
1 jest szczególnie przydatny, gdy definiujesz wyrażenia regularne algebraicznie. 1 to pusty ciąg, 0 to pusty język, konkatenacja to a union to + , a otrzymasz pół-pierścień. czyni to jednak nieco bardziej skomplikowanym. +
jmite

Dziękuję za Twoją odpowiedź! Wydaje się to prawdopodobne, więc szukam referencji. Ponieważ artykuł Formal Language z Wikipedii mówi, że geneza FL pochodzi od Begottsschrift Gottloba Frege'a (1879), dziś czytam przetłumaczoną wersję, ale wydaje się, że nie używa notacji λ. Inna historyczna praca Emurs Post (1947) Recursive Unsolvability of a Problem of Thue . Dlatego ciągle szukam. W każdym razie dzięki za wielką pomoc :)
nekketsuuu,

8

Prawdopodobnie zapis pochodzi z „szkoły fińskiej”.

λ

Λ

Jednym z pierwszych ludzi, którzy pisali na automatach skończonych, był Trakhtenbrot i użył symbolu podobnego do ale składu jako (jak w swojej książce z Barzdinem z 1970 r. Mój rosyjski jest kiepski, ale rozumiemΛp=p=p


4
IIRC w Principia Mathematica (około 1910 r.) Russell użył do pustego zestawu. Nie mam pojęcia, czy jest to jakoś powiązane. Λ
chi

ΛΛ
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.