kompleksitas setengah bahasa

Untuk bahasa lebih , mendefinisikan Dengan kata, terdiri dari semua yang ada panjang yang sama seperti yang . $L$ $\Sigma^*$

L_{1 / 2} = {x \in Σ^{*} : x y \in L, y \in Σ^{| x |}} .

$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$

L_{1 / 2}

$L_{1/2}$

x

$x$

y

$y$

x y \in L

$xy\in L$

Latihan dalam buku Sipser ini meminta untuk menunjukkan bahwa adalah biasa setiap kali adalah. Saya telah melihat dua solusi yang berbeda, dan keduanya melibatkan ledakan negara secara eksponensial. $L_{1/2}$ $L$

Pertanyaan: kaleng siapa pun membangun sebuah keluarga bahasa sehingga otomat kanonik untuk secara signifikan (katakanlah, secara eksponensial) yang lebih besar dari itu untuk ? Upaya terbaik saya sejauh ini hanya meningkatkan ukuran negara oleh ! $\{L_n\}$ $(L_n)_{1/2}$ $L$ $+1$

fl.formal-languages automata-theory Aryeh
sumber

Anda tidak menyebutkan masalah minimisasi minimisasi DFA. belum melihat buktinya tapi mungkin mereka tidak menerimanya. dan minimalisasi DFA pasca-berjalan pada konstruksi bukti mungkin menyederhanakan DFA secara signifikan ...?

vzn

Konstruksi dalam bukti adalah abstrak dan sama sekali tidak jelas bagaimana cara meminimalkannya melalui teknik standar.

Aryeh

Bisakah Anda memposting rumpun bahasa terbaik yang Anda temukan?

Diego de Estrada

ini bukan reqd untuk menjawab Q Anda tetapi mungkin membantu untuk membuat sketsa konstruksi. Pilihan lain adalah menyerang masalah secara empiris dengan FSM acak

vzn

kompleksitas setengah bahasa

Jawaban: