Densitas asimtotik dari tata bahasa bebas ambigu konteks (CFG)

Apa rasio CFG ambigu dengan semua CFG ?

Karena kedua himpunan ini tak terhingga tak terhingga rasionya tidak terdefinisi dengan baik. Tapi bagaimana dengan kepadatan asimptotik :

lim_{n \mapsto \infty} \frac{# ambiguous CFG of size < n}{# CFG of size < n}

$\lim_{n \mapsto \infty}\frac {\# \text{ ambiguous CFG of size} < n} {\# \text{ CFG of size} < n}$

di mana simbol terminal dan non-terminal berasal dari himpunan yang dapat dihitung tetap.

Ukuran tata bahasa adalah gagasan tentang ukuran untuk tata bahasa, misalnya

jumlah total kemunculan variabel dan terminal dalam aturan produksi, atau
jumlah total kemunculan variabel, atau
jumlah total aturan produksi, atau
jumlah variabel yang berbeda.

(Saya mengasumsikan definisi ukuran tidak akan mempengaruhi jawabannya.)

fl.formal-languages grammars context-free pengguna18064
sumber

Selain itu, gagasan tentang ukuran CFG berikut telah dipertimbangkan dalam literatur: Mengenai gagasan tentang ukuran tata bahasa, berikut ini telah muncul dalam literatur. (1) Jumlah total kemunculan variabel dan terminal di kedua sisi dari semua produksi dalam tata bahasa. (2) Jumlah kejadian variabel di kedua sisi dari semua produksi dalam tata bahasa. (3) Jumlah produksi dalam tata bahasa. (4) Jumlah variabel berbeda dalam tata bahasa.

Martin Berger

Lihat misalnya: S. Ginsburg, N. Lynch, Kompleksitas Ukuran dalam Bentuk Tata Bahasa Bebas Konteks. J. Gruska, Tentang ukuran tata bahasa bebas konteks. J. Gruska, Kompleksitas dan Ketidakjelasan Tata Bahasa dan Bahasa Bebas Konteks. A. Kelemenova, Kompleksitas Tata Bahasa Bentuk Normal.

Martin Berger

@ Martin, jika seseorang tidak berhati-hati maka ada banyak tata bahasa yang berbeda secara sintaksis dengan ukuran yang diberikan dan rasionya tidak masuk akal. Cara yang aman adalah dengan menghitung panjang bit dari beberapa pengodean tata bahasa yang telah diperbaiki.

Kaveh

Anda mungkin ingin mendefinisikan kerapatan asimptotik sebagai rasio logaritma dari masing-masing kuantitas, karena kedua kuantitas bersifat eksponensial, mungkin dengan basis yang berbeda.

mobius dumpling

@ MartinBerger Dengan asumsi kita berbicara tentang hal yang sama, yaitu mendefinisikan , ini jelas akan mempengaruhi kepadatan. Misalkan jumlah CFG yang tidak ambigu adalah dan jumlah CFG adalah , maka log-density adalah sedangkan kepadatan asymptotic adalah 0. Saya cukup yakin bahwa kepadatan asimtotik akan menjadi baik 0 atau 1, tetapi kepadatan log asimptotik cenderung menjadi angka yang menarik.

l o g d e n s i t y = l o g (# u n a m b i g u o u s C F G s) / l o g (# C F G s)

$logdensity = log(\#unambiguousCFGs) / log(\#CFGs)$

{1.5}^{n}

$1.5^n$

2^{n}

$2^n$

l o g_{1.5} 2

$log_{1.5} 2$

mobius dumpling

Jawaban:

Pertanyaannya tergantung pada pengkodean yang tepat. Namun, tampaknya dalam banyak penyandian yang masuk akal, karena panjangnya cenderung tak terhingga, jumlah aturan produksi (untuk interpretasi yang tepat dari simbol awal dan terminal ) akan lebih dari satu dengan probabilitas tinggi; di sini maksud saya terminal yang sama . Jika kita menganggap ini sebagai ambiguitas, maka saya berharap tata bahasa "kebanyakan" akan ambigu. Kami juga dapat menyusun situasi yang serupa seperti aturan dan masing masing muncul setidaknya satu kali. $S\to a$ $S$ $a$ $a$ $S\to S$ $S\to a$

Dengan asumsi hipotesis umum ini, bahwa setiap aturan (tetap) yang dapat dipikirkan akan muncul dengan probabilitas tinggi karena panjangnya cenderung tak terhingga, kami menemukan bahwa "sebagian besar" tata bahasa menghasilkan dengan cara yang ambigu. $\Sigma^*$

Sebagai contoh, perhatikan pengodean berikut untuk tata bahasa di atas . Alfabet tata bahasa terdiri dari simbol . Non-terminal diindeks oleh string biner dengan panjang minimal 2. Aturan dipisahkan oleh stop penuh. Setiap aturan adalah urutan string biner yang dipisahkan oleh titik koma. String biner pertama adalah non-terminal di sisi kiri, dan sisanya (jika ada) merupakan sisi kanan; jika string biner pertama bukan non-terminal (yaitu, , 0,1), maka non-terminal awal diasumsikan. Awal non-terminal selalu 00. $\Sigma = \{0,1\}$ $\{0,1,;,.\}$ $\epsilon$

Di bawah pengkodean ini, setiap string di Menjelaskan beberapa tata bahasa. Tata bahasa acak akan dengan probabilitas tinggi mengandung banyak salinandan, dan khususnya akan ambigu. $\{0,1,;,.\}^*$ $.00;00.$ $.00;0.$

Yuval Filmus
sumber

Ya, saya menganggap aturan seperti dan (muncul lebih dari sekali) dalam tata bahasa sebagai valid. Memang, ini membuat tata bahasa sepele ambigu. Bersulang.

S \to S

$S\to S$

S \to a

$S\to a$

user18064

Tetapi bukankah demikian halnya bahwa, ketika ukuran (CFG) meningkat, jumlah terminal dan non-terminal biasanya meningkat, jadi kita membutuhkan lebih banyak bit untuk mewakili mereka, maka kita membutuhkan lebih banyak bit untuk mewakili aturan individual. Jadi jumlah CFG yang tidak ambigu untuk alasan sepele (misalnya hanya satu aturan yang cocok dengan ukuran terikat) juga meningkat.

Martin Berger

@ Martin Ini tergantung pada pengkodean. Mungkin Anda bisa membuat encoding yang mendukung klaim Anda, misalnya jika ukuran alfabet tumbuh dengan ukuran tata bahasa. Pengodean saya menggunakan ukuran alfabet yang konstan, sehingga efek ini tidak terjadi.

Yuval Filmus

@ MartinBerger Itu adalah poin yang valid tentang peningkatan jumlah simbol terminal dan non-terminal saat kita meningkatkan ukuran tata bahasa. Untuk kasus penggunaan seperti bahasa pemrograman, itu masuk akal.

user18064

@ user18064 Bahasa pemrograman biasanya menggunakan alfabet ukuran konstan, dalam kebanyakan kasus subset ASCII. Saya tidak mengetahui adanya bahasa praktis dengan ukuran alfabet tak terbatas, meskipun orang dapat dengan mudah mendefinisikannya.

Yuval Filmus