Membuktikan bahwa bahasa itu teratur atau tidak teratur

Membiarkan $L$ menjadi bahasa biasa. Buktikan bahwa:

$L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$

$L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$

$L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

teratur dan:

$L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

tidak teratur.

Tampaknya sangat sulit bagi saya. Saya kira 1-3 serupa (tapi saya mungkin salah), tetapi saya tidak tahu bagaimana cara mendekati. Gagasan umum biasanya untuk memodifikasi mesin keadaan hingga $L$ untuk menerima bahasa lain. Tetapi konstruksi itu seringkali sangat canggih dan saya masih tidak bisa memunculkannya sendirian.

regular-languages xan
sumber

kemungkinan duplikat dari Bagaimana membuktikan bahwa suatu bahasa tidak teratur?

Bartosz Przybylski

Saya tidak yakin bahwa pernyataan Anda benar karena tampaknya dengan teorema Myhill – Nerode bahwa tiga bahasa pertama memiliki banyak kelas kesetaraan! untuk yang pertama: ambil

w_{i}

$w_i$ menjadi i-th in

L_{+ - -}

$L_{+--}$ dan

w_{i + 1}

$w_{i+1}$ menjadi kata (i +1) maka untuk setiap i seseorang dapat memilih

u_{i}

$u_i$ untuk menunjukkan bahwa ada kata yang memisahkan kelas

w_{i}

$w_i$ dan

w_{i + 1}

$w_{i+1}$

Fayez Abdlrazaq Deab

@Fayez Bagaimana jika, misalnya,

L = Σ^{*}

$L=\Sigma^*$ ? Kemudian

L_{+ - -} = Σ^{*}

$L_{+--} = \Sigma^*$ hanya memiliki satu kelas kesetaraan. Periksa bukti Anda dan lihat apa yang salah.

Yuval Filmus

@ Bartek dan yang lainnya memilih untuk menutup: setengah dari pertanyaan sebenarnya adalah tentang membuktikan bahwa operasi tertentu pada bahasa menghemat properti menjadi biasa.

Yuval Filmus

Jawaban:

Berikut ini adalah bukti bahasanya $L_0 = \{ w : \exists_u |u|=|w| \land uw \in L \}$ teratur. Itu dapat dimodifikasi untuk menunjukkan bahwa tiga yang pertama pada daftar Anda adalah teratur. (Perhatikan bahwa saya berubah $wu$ untuk $uw$ .) Diberi DFA untuk $L$ , kami membuat NFA untuk $L_0$ . Hal pertama yang dilakukan NFA adalah menebak (ambil a $\epsilon$ pindah) suatu negara $q$ , yang semantik yang dimaksud adalah negara tujuan DFA $L$ berakhir setelah membaca $u$ . Kemudian secara bersamaan menjalankan dua salinan DFA untuk $L$ , yang satu dimulai pada kondisi awal dan yang lainnya dimulai pada $q$ . Saat membaca simbol $a$ , Bergerak sesuai dengan simbol sembarang pada yang pertama, dan bergerak menurut $a$ pada yang kedua. Suatu negara menerima jika salinan pertama dalam keadaan $q$ dan yang kedua adalah pada negara penerima.

Untuk yang terakhir, pertimbangkan bahasanya $L= a^+ b^+ c^+$ , dan berpotongan $L_{+-+}$ dengan $a^+ c^+$ .

Yuval Filmus
sumber

Saya tidak melihat itu.

L = a^{+} b^{+} c^{+} \Rightarrow L_{+ - +} \cap a^{+} c^{+} = {a^{n} c^{m} : n + m \equiv_{2} 0}

$L=a^+b^+c^+ \Rightarrow L_{+-+} \cap a^+c^+=\left\{ a^n c^m: n+m\equiv_2 0 \right\}$ , yang jelas merupakan bahasa reguler. Tapi saya kira saya salah :) Bisakah Anda menunjukkan saya arah yang benar?

xan

Saya telah berhasil mengubah konstruksi Anda

L_{0}

$L_0$ dan bahkan menghapus

ε

$\varepsilon$ bergerak sehingga menjadi lebih elegan (menurut saya). Jadi tiga masalah pertama diselesaikan dan terima kasih untuk itu! :) Tapi satu-satunya hal yang saya minta adalah untuk mengklarifikasi yang terakhir dan keprihatinan saya dalam komentar di atas. Saya akan sangat berterima kasih.

xan

Saat saya menghitung

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+} \cap a^+ c^+$ Saya mendapatkan sesuatu yang lain. Perhatikan bahwa setiap kata dalam

L

$L$ harus mengandung a

b

$b$ .

Yuval Filmus

Maaf, tapi saya tidak tahu bagaimana cara menghitung

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+}\cap a^+c^+$ . Saya kira hasilnya adalah

{a^{n} c^{n} : n \in N}

$\left\{ a^n c^n: n\in\mathbb{N}\right\}$ yang memberi kita apa yang kita inginkan, tetapi saya tidak tahu bagaimana membenarkan itu.

xan

Oke, saya bisa melihat sekarang :-)

xan