Apakah ada metode yang dikenal untuk membangun tata bahasa yang diberikan serangkaian string terbatas?

10

Dari bacaan saya tampaknya sebagian besar tata bahasa berkaitan dengan menghasilkan string yang tak terbatas. Bagaimana jika Anda bekerja sebaliknya?

Jika diberi n string dengan panjang m, harus dimungkinkan untuk membuat tata bahasa yang akan menghasilkan string itu, dan hanya string itu.

Apakah ada metode yang dikenal untuk melakukan ini? Idealnya nama teknik yang bisa saya teliti. Atau, bagaimana saya bisa melakukan pencarian literatur untuk menemukan metode seperti itu?

formal-languages regular-languages formal-grammars finite-sets Gustav Bertram
sumber

5

Sepele: Bangun tabel BNF dari string.

Yosua

String terbatas oleh definisi. Dan Anda tidak bisa mendapatkan set yang tak terbatas menjadi "diberikan" kecuali Anda memiliki deskripsi yang terbatas.

vonbrand

11

Ini termasuk dalam topik umum "induksi tata bahasa"; mencari frasa itu akan menghasilkan banyak literatur. Lihat, misalnya, Mendorong tata bahasa gratis konteks , https://en.wikipedia.org/wiki/Grammar_induction , https://cstheory.stackexchange.com/q/27347/5038 .

Untuk bahasa reguler (bukan yang bebas konteks), lihat juga Apakah regex golf NP-Complete? , DFA terkecil yang menerima string yang diberikan dan menolak string yang diberikan lainnya , Apakah ada peningkatan pada algoritma Dana Angluin untuk mempelajari set reguler , dan https://cstheory.stackexchange.com/q/1854/5038 .

DW
sumber

Mendorong tata bahasa untuk bahasa reguler yang mungkin tidak terbatas adalah sulit dan sangat berbeda dari masalah ini.

reinierpost

Saya menandai pertanyaan ini dengan benar, karena meskipun tidak langsung menjawab pertanyaan (yang ternyata sepele seperti yang dinyatakan), itu memberi saya jenis terminologi yang perlu saya lakukan penelitian lebih lanjut.

Gustav Bertram

8

$S=\{s_1,s_2....s_m\}$ $A$ $A \to s_1|s_2|...s_n$

sashas
sumber

Saya pikir saya perlu meninjau buku teks parsing saya. Dalam retrospeksi jawaban ini tampak jelas. Terima kasih!

Gustav Bertram

3

Ada banyak cara, jadi Anda perlu memaksakan kriteria tambahan pada kualitas hasil.

$w$ $S \rightarrow w$ $S$
$w$ $X_w$ $w_1xw_2$ $x$ $X_{w_1} \rightarrow xX_{w_2}$ $w$ $X_w \rightarrow \epsilon$ $X_\epsilon$
Pohon sufiks: sama, terbalik.
Menerapkan algoritma yang dijamin menghasilkan tata bahasa dengan ukuran minimal, misalnya dengan jumlah aturan minimal. Saya tidak tahu seberapa sulit ini.

reinierpost
sumber

Ya, setelah jawaban pertama jelas saya seharusnya memberlakukan kriteria tambahan, tetapi rasanya tidak adil untuk mengubah pertanyaan setelah jawaban pertama.

Gustav Bertram

Namun, saya ingin mengetahui kerumitan waktu dalam menemukan tata bahasa minimal untuk serangkaian string terbatas yang diberikan ... katakanlah, dalam total panjang string, atau dalam total panjang hasilnya.

reinierpost

3

Yang Anda tanyakan mirip dengan indeks pencarian. Memang Finite State Transducers dapat dibuat dan digunakan untuk mengenali teks yang diumpankan ke mereka. Sebagai contoh, Lucene menggunakan algoritma ini: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698

Untuk penggunaan praktis, lihat posting blog ini oleh Andrew Gallant: Indeks 1.600.000.000 Keys dengan Automata dan Rust

Dalam posting dia menjelaskan metode untuk membangun FSA diberikan kumpulan teks sehingga mengenali semua kata. Hasil akhirnya adalah untuk membangun FST sekitar minimal dari kunci pra-diurutkan dalam waktu linier dan dalam memori konstan.

Implementasinya tersedia di fstperpustakaannya: https://github.com/BurntSushi/fst

lkraider
sumber

1

Jawaban atas pertanyaan yang diajukan oleh reinierpost yang juga menjawab pertanyaan asli:

Kami membuat otomat kamus sebagai berikut:

buat otomat yang membaca dan menerima persis string pertama.
untuk string berikutnya, mulailah membacanya dengan automaton hingga beberapa huruf tidak ada transisi. mulai cabang baru untuk sisa string. ulangi sampai semua string diproses

Ukuran maksimal automaton adalah panjang total string input. Dengan asumsi bahwa Anda dapat mensimulasikan transisi dan membuat yang baru dalam waktu yang konstan, runtime juga merupakan panjang total dari string input. Tidak ada kasus terbaik atau terburuk.

Otomat ini minimal. karena dalam kasus biasa automata dan tata bahasa berhubungan hampir satu banding satu, hal yang sama berlaku untuk tata bahasa, Tentu saja, tidak mungkin untuk membangun sesuatu dengan ukuran n dalam waktu kurang dari n waktu.

Peter Leupold
sumber

Terima kasih. Sejauh menjawab pertanyaan ini: Saya tidak melihat apa yang dikontribusikan ini lebih dari reinierpost. Kami juga tidak ingin jawaban yang menanggapi atau mengomentari jawaban lain: ini bukan forum diskusi. Cara untuk melakukannya adalah dengan memposting pertanyaan baru dan kemudian menjawabnya sendiri. Saya menyadari itu mungkin tidak jelas. [Yang mengatakan, aku tidak melihat bagaimana jawabanmu menjawab masalah yang diinginkan oleh reinierpost. Masalah pada akhir jawaban reinierpost adalah menemukan tata bahasa dengan jumlah aturan minimum. Jawaban Anda menunjukkan bagaimana membangun DFA dengan jumlah negara minimal. (lanjutan)

DW

1

Tentu saja kita dapat mengubah DFA itu menjadi tata bahasa biasa, tetapi apa yang membuat Anda berpikir itu akan menjadi minimal dalam hal jumlah aturan dalam tata bahasa? Sepertinya itu perlu bukti.]

DW

Apa yang dikontribusikan jawaban saya adalah runtime, saya pikir. Anda benar, beberapa hal yang saya katakan perlu beberapa bukti. Tetapi korespondensi antara transisi Finite Automata dan aturan Tata Bahasa Reguler sangat jelas bagi saya (jika yang terakhir hanya dapat menghasilkan satu terminal per aturan seperti dalam kebanyakan definisi); maka setiap tata bahasa yang lebih kecil dari milikku akan memberikan otomat yang lebih kecil dari yang minimal. Jadi saya pikir tata bahasa dari otomat minimal (saya tidak membuktikan bahwa saya minimal) akan minimal juga. - Saya akan menyimpan saran Anda mengenai jawaban dalam pikiran, terima kasih

Peter Leupold

Gagasan minimal untuk DFA adalah sehubungan dengan jumlah negara . Apakah ini menyiratkan minimal sehubungan dengan jumlah transisi dalam DFA, atau minimal jumlah aturan dalam tata bahasa yang dihasilkan? Saya pikir kita harus melacak apa metrik Anda, karena kalau tidak, saya khawatir kita akan membandingkan apel dengan jeruk.

DW

Benar, Tata bahasanya akan minimal di termson non-terminal. Untuk aturan, ini tidak jelas.

Peter Leupold

Apakah ada metode yang dikenal untuk membangun tata bahasa yang diberikan serangkaian string terbatas?

Jawaban: