Bintangi bahasa gratis vs bahasa biasa

Saya bertanya-tanya, karena itu sendiri adalah bahasa bebas bintang, adakah bahasa biasa yang bukan bahasa bebas bintang? Bisakah Anda memberi contoh?$a^*$

(dari wikipdia ) Lawson mendefinisikan bahasa bebas bintang sebagai:

Bahasa reguler dikatakan bebas bintang jika dapat dijelaskan dengan ekspresi reguler yang dibangun dari huruf-huruf alfabet, simbol himpunan kosong, semua operator boolean - termasuk pelengkap - dan penggabungan tetapi tidak ada bintang Kleene.

Ini adalah bukti bebas bintang:$a^*$

$\emptyset$⟹ Σ ∗ = ˉ ∅ ⟹ A ⊆ Σ Σ ∗ A Σ ∗ ⟹ A ⊆ Σ A ∗ = ¯ Σ ∗ ( Σ ∖ A ) Σ ∗ bebas-bintang bebas-bintang Jika maka bebas-bintang Jika maka bebas bintang$\Longrightarrow$
$\Sigma^*=\bar{\emptyset}$$\Longrightarrow$
$A\subseteq\Sigma$$\Sigma^*A\Sigma^*$$\Longrightarrow$
$A\subseteq\Sigma$$A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$

Pada baris terakhir kita memiliki , karena kata apa pun yang bukan dari bentuk berisi huruf dalam dan sebaliknya.$A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$$A^*$$\Sigma \setminus A$

Bahasa reguler adalah bahasa yang dapat dijelaskan oleh logika urutan kedua monadik lemah (WMSO) [1].

Bahasa bebas bintang adalah bahasa yang dapat dijelaskan dengan logika urutan pertama dengan $<$ (FO [<]) [2].

Kedua logika itu tidak sama kuatnya. Salah satu contoh untuk bahasa yang WMSO-didefinisikan tetapi tidak FO [<] - didefinisikan adalah (yang jelas regular³); ini dapat ditunjukkan menggunakan game Ehrenfeucht-Fraissé ⁴.$(aa)^*$

1. Lemah Aritmatika Orde Kedua dan Automata Terbatas oleh Büchi (1960)
2. Automata bebas-counter oleh McNaughton dan Papert (1971)

3. Sebuah WMSO-rumus untuk adalah$(aa)^*$

   $\ \begin{align} \bigl[ \forall x. P_a(x)\bigr] \land \Bigl[ \exists x. P_a(x) \to \bigl[ \exists X. X(0) &\land [\forall x,y. X(x) \land \operatorname{suc}(x,y) \to \lnot X(y)] \\ &\land [\forall x,y. \lnot X(x) \land \operatorname{suc}(x,y) \to X(y)] \\ &\land [\forall x. \operatorname{last}(x) \to \lnot X(x)] \bigr] \Bigr] \;. \end{align}$

   (Jika kata itu tidak kosong, adalah himpunan semua indeks genap.)$X$

4. Lihat juga di sini .

Schützenberger (1965) memberikan karakterisasi aljabar dari bahasa bebas bintang: bahasa reguler bebas bintang jika dan hanya jika mono sintaksisnya adalah aperiodik. Berlawanan dengan karakterisasi logis (bebas bintang = FO [<]), karakterisasi aljabar ini memberikan algoritma untuk memutuskan apakah bahasa reguler yang diberikan adalah bebas bintang (bahasa biasa dapat diberikan oleh otomat terbatas, ekspresi reguler, atau tata bahasa reguler). Dengan menggunakan karakterisasi logis (karena McNaughton dan Papert) seseorang kemudian dapat memutuskan masalah berikut: diberi rumus WMSO, apakah ada rumus FO yang menggambarkan bahasa yang sama?

M.-P. Schützenberger, Pada monoida terbatas hanya memiliki subkelompok sepele, Informasi dan Kontrol 8 (1965), 190-194.

R. ~ McNaughton dan S. ~ Papert, automata bebas-kontra, The MIT Press, Cambridge, Massa-London, 1971.

Bukti lengkap teorema Schützenberger dapat ditemukan di berbagai buku teks atau makalah survei. Untuk presentasi dasar dari algoritma yang sesuai (tanpa bukti), lihat

J.-É. Pin, semigroup terbatas dan bahasa yang dikenal: pengantar, dalam Semigroup Institut Studi Lanjut NATO, Bahasa dan Grup Formal , J. Fountain ()d.), 1-32, penerbit akademik Kluwer, (1995).

Bahasa bebas bintang dijelaskan oleh ekspresi reguler yang mencakup gabungan, pelengkap, penyatuan, persimpangan, tetapi tanpa bintang-Kleene.

Karena bahasa reguler ditutup di bawah semua operasi ini (di mana pelengkap adalah titik penting), maka setiap bahasa bebas bintang juga teratur.

Mungkin maksud Anda yang sebaliknya? Apakah semua bahasa reguler bebas bintang? Jawaban untuk yang terakhir adalah tidak. Lihat makalah ini untuk detailnya.

Contoh pemisahan sederhana adalah (aa) *. Lebih canggih: Semua string biner dengan paritas genap (atau ganjil).