Operasi bintang Kleene pada bahasa kosong

Dalam buku teks saya disebutkan bahwa: mana adalah bahasa kosong. $\emptyset^*=\{\epsilon\}$ $\emptyset$

Namun, kita tahu bahwa $L \cdot \emptyset = \emptyset$ , di mana $L$ adalah Bahasa apa pun.

Saya tidak dapat memahami konsep ini secara intuitif karena operasi bintang Kleene menunjuk pada fakta bahwa $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$ .

Jadi mengapa $\emptyset^*$ tidak sama dengan $\emptyset$ ?

formal-languages kleene-star Sagnik
sumber

Lihat jawaban ini . Pada dasarnya, untuk setiap set

tidak kosong ,

untuk konsistensi rumus

. Ini diperluas ke kasus ketika

sebagai ekstensi yang lebih alami. Ini adalah pilihan biasa dalam semi-ring. Sisanya mengikuti dari definisi bintang Kleene.

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$

babou

Namun, untuk angka,

dibiarkan tidak terdefinisi, sebagian besar karena masalah continuty seperti yang saya ingat, meskipun mungkin lebih mudah untuk mendefinisikannya sama dengan

. Lihat

0^{0}

$0^0$

1

$1$

0^{0}

$0^0$

babou

Hanya karena

untuk semua , menurut definisi.

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

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

Raphael

@ Raphael Ya. Anda bisa bicara seperti itu. Tapi itu arbitrary, afaik, ketika

. Saya mungkin harus menulis jawaban saya secara berbeda. Saya berusaha terlalu keras untuk menjelaskan.

L = \emptyset

$L=\emptyset$

babou

@ Babou Pada akhirnya, setiap definisi berubah-ubah. Beberapa definisi sangat membantu, yang lain tidak. Imho, mencoba menemukan intuisi dalam definisi yang mendasar seperti ini jarang membantu, dan kadang-kadang berbahaya.

Raphael

Jawaban:

Jika Anda sekarang mempertimbangkan kekuatan bahasa Anda memiliki Jika Anda ingin ini konsisten dengan , yaitu bilangan bulat non-negatif, Anda harus mendefinisikan . Jika Anda menganggapnya Anda akan memiliki termasuk, antara lain, untuk $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$ . Dengan demikian kita akan memiliki untuk setiap . Jadi ini jelas tidak konsisten. Ketidakkonsistenan serupa muncul untuk pilihan lain selain , yang merupakan identitas untuk rangkaian bahasa. $x=1$ $W^1=W=\emptyset$ $W$ $\{\epsilon\}$

Oleh karena itu, definisi konsisten hanya konsisten untuk kosong set non adalah . $W^0$ $W$ $W^0=\{\epsilon\}$

Maka mudah untuk memperluas definisi ke kasus ketika sebagai . $W=\emptyset$ $\emptyset^0=\{\epsilon\}$

Ini hanya definisi yang konsisten dan nyaman, sering diadopsi dalam semi-ring tetapi tidak dapat dibuktikan, tidak seperti halnya ketika mana tidak ada definisi konsisten lainnya. $W\neq\emptyset$

Namun, definisi lain kemudian harus diberikan secara konsisten, yang menyiratkan hal itu

\begin{aligned} \emptyset^{*} & = \emptyset^{0} \cup \emptyset^{1} \cup \emptyset^{2} \cup \dots \\ = {ϵ} \cup \emptyset \cup \emptyset \cup \dots \\ = {ϵ} \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$

Setengah lingkaran bahasa dijelaskan dalam jawaban ini .

babou
sumber

Jawaban ini menghapus semua keraguan saya. Dan tautannya sangat bagus.

Sagnik

$\emptyset$ $\epsilon$ $\epsilon \in \emptyset^*$ $L$ $L^*$ $L$

Yuval Filmus
sumber

Saya mencari penjelasan yang lebih matematis karena saya tidak bisa mendapatkan pemahaman intuitif tentang konsep "gabungan kata-kata nol". Namun setelah membaca jawaban @ babou dan jawaban ini semua keraguan saya hilang. Terima kasih.

Sagnik

"... untuk bahasa L, bintang Kleene L * terdiri dari semua gabungan dari sejumlah kata dari L, angka apa pun termasuk nol kata" Di sini, bagaimana nol jumlah kata menyiratkan eplison? epsilon adalah sebuah kata, jadi bagaimana kita dapat mengatakan bahwa nol jumlah kata termasuk epsilon? Tolong perbaiki saya.

Palak Jain

Rangkaian kata-kata nol adalah elemen netral untuk rangkaian kata, yang merupakan kata kosong. Dengan cara yang sama, jumlah elemen nol adalah nol, produk elemen nol adalah satu, penyatuan set nol adalah set kosong, dan seterusnya.

Yuval Filmus