Грамматика с эпсилонами или лямбдами

Question

Итак, у меня есть набор грамматик

S -> X Y
X -> a X
X -> 
Y -> b
Z -> a Z
Z -> a

Меня только смущает эта грамматика в том, что 2nd Production for X

Там ничего нет.Является ли это эквивалентом использования Epsilon ε или Lamda λ

Я предполагаю, что это просто разница в обозначениях для грамматик, но я хотел быть уверен, поскольку я пытаюсь построить первый и последующий наборы

Answer 1

И ε, и λ (а иногда и Λ) используются разными авторами для представления пустой строки.В современной письменности ε встречается гораздо чаще, но вы часто найдете λ в более старых учебниках, а Λ - даже в более старых.

Смысл использования этих символов состоит в том, чтобы сделать пустую последовательность видимой.Как бы там ни было написано, это пустая последовательность, и ее следует читать, как если бы она была ничем, как в вашей постановке X ⇒ .

---

Если вам трудно понять, чтосимвол ничего не значит, тогда вам может понравиться чтение «1007 * ноль» Чарльза Сейфа: «Биография опасной идеи» или «1009 *« Ничего, что есть: естественная история нуля »Чарльза * 1010, оба опубликованные в символическомгод 2K и оба они исследуют долгую и трудную борьбу, чтобы понять концепцию ничего.(«Никто не выходит, чтобы купить нулевую рыбу» - Альфред Норт Уайтхед).

---

Было высказано предположение, что Λ / λ происходит от немецкого слова «leer», что означает пустой, а ε приходитс английского "пусто".Было время, когда немецкий язык более распространен в академической дискуссии по математической логике, поэтому теория кажется разумной.