Kami mendefinisikan bahasa pohon biasa seperti dalam buku TATA : Ini adalah kumpulan pohon yang diterima oleh otomat pohon terbatas non-deterministik (Bab 1) atau, setara, serangkaian pohon yang dihasilkan oleh tata bahasa pohon biasa (Bab 2). Kedua formalisme memiliki kemiripan yang erat dengan analog string yang terkenal.
Apakah ada bahasa pohon reguler di mana tinggi rata-rata pohon ukuran bukanlah atau ?
Jelas ada bahasa pohon sedemikian rupa sehingga ketinggian pohon linear dalam ukurannya; dan dalam buku Combinatorics Analytic ditunjukkan misalnya bahwa pohon biner berukuran memiliki tinggi rata-rata . Jika saya memahami Proposisi VII.16 (hal.537) dari buku yang disebutkan dengan benar, maka ada subset luas dari bahasa pohon reguler yang memiliki tinggi rata-rata , yaitu yang menggunakan bahasa pohon juga merupakan varietas pohon sederhana yang memenuhi beberapa kondisi tambahan.
Jadi saya bertanya-tanya apakah ada bahasa pohon reguler yang menunjukkan ketinggian rata-rata yang berbeda atau apakah ada dikotomi sejati untuk bahasa pohon biasa.
Catatan: Pertanyaan ini telah diajukan sebelumnya pada Ilmu Komputer , namun belum dijawab selama lebih dari tiga bulan. Saya ingin memposting ulang di sini karena pertanyaannya terlalu lama untuk dimigrasi dan karena masih ada minat pada pertanyaan itu. Berikut ini tautan ke pos asli.
Jawaban:
Saya percaya bahwa jawabannya adalah seperti yang Anda sarankan bahwa tidak ada asimptotik selain , dan adalah mungkin. Rute yang menjanjikan untuk membuktikan ini bisa dengan menerapkan teknik dari makalah yang menurunkan asimtotik ke pohon run dari bahasa biasa. Perhatikan bahwa sebuah pohon diterima jika ada pohon run sehingga harus dimungkinkan untuk terlebih dahulu menurunkan (menggunakan loc.cit. ) Ketinggian rata-rata pohon run yang dihasilkan secara acak dan mengambilnya dari sana, yaitu menunjukkan bahwa memproyeksikan jauh negara tidak tidak mengubah ketinggian rata-rata.Θ(1) Θ(n−−√) Θ(n) Θ(n−−√)
sumber