Hierarki dalam bahasa reguler

Apakah ada hierarki "baik" yang diketahui (mungkin terbatas) di dalam kelas bahasa reguler ? Dengan baik di sini, kelas-kelas di setiap hierarki menangkap ekspresifitas / kekuatan / kompleksitas yang berbeda. Juga, keanggotaan masing-masing kelas "baik" ditunjukkan oleh beberapa elemen (tidak seperti masalah ketinggian bintang yang mungkin bermasalah).$L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$$L$

Terima kasih!

Berikut adalah daftar beberapa hierarki minat, beberapa di antaranya sudah disebutkan dalam jawaban lain.

1. Hirarki konkatasi

Sebuah bahasa adalah produk ditandai dari jika untuk beberapa surat . Hirarki konkatasi didefinisikan dengan bergantian operasi Boolean dan operasi polinomial (= gabungan dan produk yang ditandai). Hirarki Straubing-Thérien (titik awal dan hierarki kedalaman-titik (titik awal dari jenis ini, tetapi Anda dapat mengambil titik awal lainnya, terutama bahasa grup (bahasa yang diterima oleh robot permutasi).L 0 , L 1 , … , L n L = L 0 a 1 L 1 ⋯ a n L n a 1 , … , a n { ∅ , A ∗ } ) { ∅ , { 1 } , A + , A ∗ } $L$$L_0, L_1, \ldots, L_n$$L = L_0a_1L_1 \cdots a_nL_n$$a_1, \ldots, a_n$$\{\emptyset, A^*\})\ $$\{\emptyset, \{1\}, A^+, A^*\})\ $

2. Hirarki bintang-tinggi

Pola umum adalah untuk menghitung jumlah minimal bintang bersarang yang diperlukan untuk mengekspresikan bahasa mulai dari huruf, tetapi beberapa varian dimungkinkan, tergantung pada operator dasar yang Anda izinkan. Jika Anda hanya mengizinkan penyatuan dan produk, Anda menentukan ketinggian bintang terbatas, jika Anda mengizinkan penyatuan, pelengkap dan produk, Anda menentukan tinggi-bintang (umum) dan jika Anda mengizinkan penyatuan, persimpangan dan produk, Anda menentukan tinggi-bintang menengah . Ada bahasa bintang terbatas untuk setiap dan aktif dapat secara efektif menghitung ketinggian bintang dari bahasa reguler yang diberikan. Untuk tinggi bintang, tinggi bintang dapat dipilih ( bahasa bebas bintang ), ada bahasa dengan tinggi bintangn 0 1 $n$$n$$0$$1$, tetapi tidak ada bahasa dengan tinggi bintang diketahui! Tidak ada hasil yang diketahui pada ketinggian bintang menengah. Lihat makalah ini untuk ikhtisar.$2$

3. Hirarki logis

Ada banyak dari mereka, tetapi salah satu yang paling penting adalah apa yang disebut hirarki . Rumus dikatakan sebagai jika setara dengan rumus bentuk mana bebas kuantifier dan adalah urutan blok quantifiers sehingga blok pertama hanya berisi quantifiers eksistensial (perhatikan bahwa blok pertama ini mungkin kosong), blok kedua quantifiers universal, dll. Demikian pula, jika adalah terbentuk dari bolak-balik kuantifikasi yang dimulai dengan blok bilangan universal (yang lagi-lagi mungkin kosong), kita mengatakan bahwaΣ n Q ( x 1 , . . . , X k ) φ φ Q ( x 1 , . . . , X k ) n Q ( x 1 , . . . , X k ) n φ Π n Σ n Π n Σ n Π n B Σ n Σ n $\Sigma_n$$\Sigma_n$$Q(x_1,...,x_k)\varphi$$\varphi$$Q(x_1,...,x_k)$$n$$Q(x_1,...,x_k)$$n$$\varphi$adalah . Mendenotasikan oleh (resp. ) kelas bahasa yang dapat didefinisikan oleh -formula (resp. A -formula) dan oleh penutupan Boolean dari -languages . Akhirnya, biarkan . Gambaran umum terlihat seperti yang satu ini tentu saja perlu menentukan tanda tangan. Biasanya ada predikat untuk setiap huruf (dan berarti ada huruf pada posisi dalam kata). Maka seseorang dapat menambahkan simbol biner$\Pi_n$$\Sigma_n$$\Pi_n$$\Sigma_n$$\Pi_n$$\mathcal{B}\Sigma_n$$\Sigma_n$a a x a x < M o d $\Delta_n = \Sigma_n \cap \Pi_n$$\mathbf{a}$$\mathbf{a}x$$a$$x$$<$(hierarki yang sesuai adalah hierarki Straubing-Thérien) dan juga simbol penerus (hierarki yang sesuai adalah hierarki titik-kedalaman). Kemungkinan lain termasuk predikat, untuk menghitung modulo , dll Lihat lagi ini kertas untuk gambaran.$Mod$$n$

4. Hierarki Boolean

Pola umum (yang tidak spesifik untuk bahasa biasa) adalah karena Hausdorff. Biarkan menjadi kelas bahasa yang berisi set kosong dan set lengkap, dan ditutup di bawah persimpangan terbatas dan gabungan terbatas. Biarkan menjadi kelas dari semua bahasa dalam bentuk mana dan . Karena , kelas mendefinisikan hierarki dan penyatuan mereka adalah penutupan Boolean dariD n ( L ) X = X 1 - X 2 + ⋯ ± X n X i ∈ L X 1 ⊇ X 2 ⊇ X 3 ⊇ ⋯ ⊇ X n D n ( L ) ⊆ D n + 1 ( L ) D n ( L ) $\mathcal{L}$$\mathcal{D}_n(\mathcal{L})$

5. Kompleksitas kelompok

Hasil dari Krohn-Rhodes (1966) menyatakan bahwa setiap DFA dapat disimulasikan oleh kaskade reset (juga disebut flip-flop) automata dan automata yang semigroup transisinya adalah grup hingga. Kompleksitas kelompok suatu bahasa adalah jumlah kelompok yang paling sedikit terlibat dalam dekomposisi DFA minimal bahasa tersebut. Bahasa kompleksitas adalah bahasa bebas bintang dan ada bahasa dengan kompleksitas apa pun. Namun, tidak ada karakterisasi efektif dari bahasa kompleksitas yang diketahui.$0$$1$

6. Hierarki diwarisi dari kompleksitas sirkuit

Titik awalnya adalah artikel bagus yang menunjukkan khususnya bahwa kelas dapat dipilih. Biarkan , di mana . Jika membagi , maka . Pertanyaan yang menarik adalah mengetahui apakah dapat dipilih untuk apa pun .A C 0 ∩ R e g A C C ( q ) = { L ⊆ { 0 , 1 } ∗ ∣ L ⩽ A C 0 M q q $[1]$$AC^0 \cap Reg$$ACC(q) = \{ L \subseteq \{0,1\}^* \mid L \leqslant_{AC^0} MOD_q\}$$MOD_q = \{u \in \{0,1\}^* \mid |u|_1 \equiv 0 \bmod q\}$$q$$q'$A C C ( q ) ∩ R e g $ACC(q) \subseteq ACC(q')$$ACC(q) \cap Reg$$q$

N C $[1]$ Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Bahasa reguler di . J. Comput. Sistem Sci. 44 (1992)$NC^1$

Memperluas komentar: hirarki alami adalah yang disebabkan oleh jumlah negara DFA.

Kita dapat mendefinisikan$\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$

( , )| Q | = $D = \{Q, \Sigma, \delta, q_0, F \}$$|Q| = n$

Jelas (cukup gunakan status mati)$\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$

Untuk memperlihatkan inklusi yang tepat kita cukup memilih bahasa: L n + 1 ={ a i ∣i≥n}∈ L n + $\mathcal{L}_n \subsetneq \mathcal{L}_{n+1}$$L_{n+1} = \{ a^{i} \mid i \geq n \} \in \mathcal{L}_{n+1}$

Sangat informal: DFA (minimum) yang mengenali harus berupa "rantai negara" dengan panjang : , dan ( memiliki self-loop). Jadi menyatakan cukup untuk menerima . Tetapi setiap jalur penerimaan dari ke keadaan akhir yang lebih pendek dari harus menerima beberapa dengan yang bukan milik , jadi DFA dengan atau lebih sedikit negara bagian yang tidak dapat meneriman + 1 q 0 → a q 1 → a . . . → a q n F = { q n } q n → a q n q n n + 1 L n + 1 q 0 q f n + 1 a i i < n L $\{ a^{i} \mid i \geq n \}$$n+1$$q_0 \to^a q_1 \to^a ... \to^a q_n$$F = \{q_n\}$$q_n \to^a q_n$$q_n$$n+1$$L_{n+1}$$q_0$$q_f$$n+1$$a^{i}$$i < n$ n L n + $L_{n+1}$$n$$L_{n+1}$ .

Saya baru-baru ini menemukan makalah ini yang dapat memberikan contoh lain yang relevan (lih. Kalimat terakhir dari abstrak):

Guillaume Bonfante, Florian Deloup: Genus bahasa reguler.

Dari abstrak: Artikel ini mendefinisikan dan mempelajari genus state deterministic automata (FSA) dan bahasa reguler. Memang, FSA dapat dilihat sebagai grafik yang muncul gagasan genus. Pada saat yang sama, FSA memiliki semantik melalui bahasa dasarnya. Maka wajar untuk membuat hubungan antara bahasa dan gagasan genus. Setelah kami memperkenalkan dan membenarkan gagasan genus untuk bahasa reguler, [...] kami membangun bahasa reguler dari genus besar yang sewenang-wenang: gagasan genus mendefinisikan hierarki yang tepat untuk bahasa reguler.

Ada beberapa hierarki alami untuk bahasa reguler kata-kata tak terbatas, yang menyampaikan gagasan "kompleksitas bahasa", misalnya:

• Jumlah peringkat yang dibutuhkan dalam otomat paritas deterministik
• Hirarki Wadge (atau Wagner): kompleksitas topologi, level .$\omega^\omega$

Hirarki ini dapat digeneralisasikan untuk bahasa reguler pohon tak terbatas, yang untuknya hierarki baru muncul, lihat misalnya jawaban ini .