Клини звездная операция на пустом языке

В моем учебнике упоминается, что: где - пустой язык. $\emptyset^*=\{\epsilon\}$ $\emptyset$

Однако мы знаем, что , где - любой язык. $L \cdot \emptyset = \emptyset$ $L$

Я не могу интуитивно понять эту концепцию, потому что операция звезды Клини указывает на тот факт, что . $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$

Так почему же не равно ? $\emptyset^*$ $\emptyset$

formal-languages kleene-star Sagnik
источник

Смотрите этот ответ . В принципе, для любого непустого множества , для согласованности формулы . Это распространяется на случай, когда как более естественное расширение. Это обычный выбор в полукольцах. Остальное следует из определения звезды Клини.

W

$W$

W^{0} = \emptyset

$W^0=\emptyset$

W^{x} W^{y} = W^{x + y}

$W^xW^y=W^{x+y}$

W = \emptyset

$W=\emptyset$

Бабу

Однако для чисел остается неопределенным, в основном из-за проблем с непрерывностью, насколько я помню, хотя часто бывает удобно определить его равным . Смотрите

0^{0}

$0^0$

1

$1$

0^{0}

$0^0$

Бабу

Просто потому, что

для всех по определению.

ε \in L^{0} = {ε}

$\varepsilon \in L^0 = \{\varepsilon\}$ $L$

Рафаэль

@ Рафаэль Да. Вы можете сказать это так. Но это произвольно, афаик, когда

. Я, вероятно, должен написать свой ответ по-другому. Я слишком стараюсь объяснить.

L = \emptyset

$L=\emptyset$

Бабу

@babou В конце концов, каждое определение является произвольным. Некоторые определения полезны, другие нет. Имхо, пытаюсь найти интуицию в основных определениях, поскольку это редко полезно, а иногда и вредно.

Рафаэль

Ответы:

Если вы теперь рассмотрите возможности языка то у вас есть Если вы хотите, чтобы это было согласованно по , то есть неотрицательным целым числам, вы должны определить . Если бы вы приняли это за вы бы имели включая, среди прочего, $W$ $W^xW^y=W^{x+y}$ $\mathbb N_0$ $W^0=\{\epsilon\}$ $\emptyset$ $W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ . Таким образоммы имеем для любого . Таким образом, это было бы явно противоречивым. Аналогичное несоответствие возникает для любого другого выбора, кроме , который является идентификатором для объединения языков. $x=1$ $W^1=W=\emptyset$ $W$ $\{\epsilon\}$

Следовательно, единственное непротиворечивое непротиворечивое определение для непустого множества - это . $W^0$ $W$ $W^0=\{\epsilon\}$

Тогда удобно распространить определение на случай, когда при . $W=\emptyset$ $\emptyset^0=\{\epsilon\}$

Это просто последовательное и удобное определение, часто принимается в полукольцами , но она не может быть доказана, в отличие от случая , когда THW , где нет другого согласованного определения. $W\neq\emptyset$

Тем не менее, другие определения должны быть даны согласованным образом, что подразумевает, что

\begin{aligned} \emptyset^{*} & знак равно \emptyset^{0} \cup \emptyset^{1} \cup \emptyset^{2} \cup ... \\ знак равно {ε} \cup \emptyset \cup \emptyset \cup ... \\ знак равно {ε} \end{aligned}

$\begin{align} \emptyset^*&=\emptyset^0\cup\emptyset^1\cup\emptyset^2\cup\ldots \\ &=\{\epsilon\}\cup\emptyset\cup\emptyset\cup\ldots\\ &=\{\epsilon\} \end{align}$

Эта тема обсуждается на многих веб-страницах. В случае полукольца чисел (отсутствие точности является преднамеренным) это подробно обсуждается на этой странице: От нуля до нулевой степени - ? $0^0=1$ ,

Полукольцо языков описано в этом ответе .

Babou
источник

Этот ответ очистил все мои сомнения. И ссылки были превосходны.

Сагник

Конкатенация нулевых слов из является пустым словом , поэтому . В более общем случае для языка звезда Клини состоит из всей конкатенации любого числа слов из , любого числа, включая нулевые слова . $\emptyset$ $\epsilon$ $\epsilon \in \emptyset^*$ $L$ $L^*$ $L$

Юваль Фильмус
источник

Я искал более математическое объяснение, потому что не мог получить интуитивное понимание концепции «объединения нулевых слов». Однако после прочтения ответа @ babou и этого ответа все мои сомнения прояснились. Спасибо.

Сагник

«... для языка L звезда Клини L * состоит из всей конкатенации любого числа слов из L, любого числа, включая ноль слов». Как же нулевое число слов означает «эплисон»? эпсилон это слово, так как мы можем сказать, что нулевое число слов включает в себя эпсилон? Поправь меня, пожалуйста.

Палак Джейн

Конкатенация нулевых слов является нейтральным элементом для конкатенации, то есть пустым словом. Точно так же сумма нулевых элементов равна нулю, произведение нулевых элементов равно единице, объединение нулевых наборов - это пустое множество, и так далее.

Юваль Фильмус