Pertanyaan yang diberi tag fl.formal-languages

bahasa formal, tata bahasa, teori automata

30
Apakah { } tidak bebas konteks?

Apakah bahasa { } bebas konteks atau tidak?aibjck | i≠j,i≠k,j≠kaibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Saya menyadari bahwa saya telah menemukan hampir semua varian pertanyaan ini dengan kondisi yang berbeda tentang hubungan antara i, j, dan k, tetapi tidak yang...

28
Kondisi untuk universalitas NFA

Pertimbangkan automata terbatas nondeterministic , dan fungsi . Selain itu kami mendefinisikan .A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F)f(n)f(n)f(n)Σ≤k=⋃i≤kΣiΣ≤k=⋃i≤kΣi\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i Sekarang mari kita menganalisis pernyataan berikut: Jika ,...

25
Memulihkan hutan parse dari pengurai Earley?

Saya baru-baru ini membaca tentang parser Earley dan berpikir itu adalah salah satu algoritma paling elegan yang pernah saya lihat sampai saat ini. Namun, algoritma dalam pengertian tradisionalnya adalah sebuah pengenal dan bukan pengurai, yang berarti bahwa ia dapat mendeteksi apakah suatu string...

24
kompleksitas setengah bahasa

Untuk bahasa lebih Σ * , mendefinisikan L 1 / 2 = { x ∈ Σ * : x y ∈ L , y ∈ Σ | x | } . Dengan kata, L 1 / 2 terdiri dari semua x yang ada y panjang yang sama seperti yang x y ∈ L .LLLΣ∗Σ∗\Sigma^*L1/2={x∈Σ∗:xy∈L,y∈Σ|x|}.L1/2={x∈Σ∗:xy∈L,y∈Σ|x|}.L_{1/2} = \{x \in \Sigma^* : xy\in L,...