Bagaimana perbedaan antara ambiguitas dengan determinisme?

13

Saya mencoba memahami apa yang dimaksud dengan "deterministik" dalam ungkapan seperti "tata bahasa bebas konteks deterministik". (Ada lebih banyak "hal-hal" deterministik dalam bidang ini). Saya akan menghargai contoh lebih dari penjelasan yang paling rumit! Jika memungkinkan.

Sumber kebingungan utama saya adalah dari tidak dapat mengatakan bagaimana properti tata bahasa ini berbeda dari ambiguitas (non-).

Yang paling dekat saya menemukan maknanya adalah kutipan dari makalah ini oleh D. Knuth On Translation of Languages ​​dari Kiri ke Kanan :

Ginsburg dan Greibach (1965) telah mendefinisikan gagasan tentang bahasa deterministik; kami menunjukkan dalam Bagian V bahwa ini adalah bahasa yang tepat untuk tata bahasa LR (k)

yang menjadi melingkar segera setelah Anda sampai ke Section V, karena di sana dikatakan bahwa apa yang dapat diurai LR (k) adalah bahasa deterministik ...


Di bawah ini adalah contoh yang bisa saya temukan untuk membantu saya memahami apa arti "ambigous", silakan lihat:

onewartwoearewe

Yang dapat diuraikan sebagai one war two ear eweatau o new art woe are we- jika tata bahasa memungkinkan itu (katakan itu memiliki semua kata yang baru saja saya daftarkan).

Apa yang harus saya lakukan untuk menjadikan contoh bahasa ini (non-) deterministik? (Saya bisa, misalnya, menghapus kata odari tata bahasa, untuk membuat tata bahasa tidak ambigu).

Apakah bahasa di atas deterministik?

PS. Contohnya adalah dari buku Godel, Esher, Bach: Eternal Golden Braid.


Katakanlah, kita mendefinisikan tata bahasa untuk contoh bahasa seperti ini:

S -> A 'we' | A 'ewe'
A -> B | BA
B -> 'o' | 'new' | 'art' | 'woe' | 'are' | 'one' | 'war' | 'two' | 'ear'

Dengan argumen tentang harus menguraikan seluruh string, apakah tata bahasa ini membuat bahasa menjadi non-deterministik?


let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) [];;

let rec woe_parser s =
  match s with
  | 'w' :: 'e' :: [] -> true
  | 'e' :: 'w' :: 'e' :: [] -> true
  | 'o' :: x -> woe_parser x
  | 'n' :: 'e' :: 'w' :: x -> woe_parser x
  | 'a' :: 'r' :: 't' :: x -> woe_parser x
  | 'w' :: 'o' :: 'e' :: x -> woe_parser x
  | 'a' :: 'r' :: 'e' :: x -> woe_parser x
  (* this line will trigger an error, because it creates 
     ambiguous grammar *)
  | 'o' :: 'n' :: 'e' :: x -> woe_parser x
  | 'w' :: 'a' :: 'r' :: x -> woe_parser x
  | 't' :: 'w' :: 'o' :: x -> woe_parser x
  | 'e' :: 'a' :: 'r' :: x -> woe_parser x
  | _ -> false;;

woe_parser (explode "onewartwoearewe");;
- : bool = true

| Label   | Pattern      |
|---------+--------------|
| rule-01 | S -> A 'we'  |
| rule-02 | S -> A 'ewe' |
| rule-03 | A -> B       |
| rule-04 | A -> BA      |
| rule-05 | B -> 'o'     |
| rule-06 | B -> 'new'   |
| rule-07 | B -> 'art'   |
| rule-08 | B -> 'woe'   |
| rule-09 | B -> 'are'   |
| rule-10 | B -> 'one'   |
| rule-11 | B -> 'war'   |
| rule-12 | B -> 'two'   |
| rule-13 | B -> 'ear'   |
#+TBLFM: @2$1..@>$1='(format "rule-%02d" (1- @#));L

Generating =onewartwoearewe=

First way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-01 | A'we'             |
| A'we'             | rule-04 | BA'we'            |
| BA'we'            | rule-05 | 'o'A'we'          |
| 'o'A'we'          | rule-04 | 'o'BA'we'         |
| 'o'BA'we'         | rule-06 | 'onew'A'we'       |
| 'onew'A'we'       | rule-04 | 'onew'BA'we'      |
| 'onew'BA'we'      | rule-07 | 'onewart'A'we'    |
| 'onewart'A'we'    | rule-04 | 'onewart'BA'we'   |
| 'onewart'BA'we'   | rule-08 | 'onewartwoe'A'we' |
| 'onewartwoe'A'we' | rule-03 | 'onewartwoe'B'we' |
| 'onewartwoe'B'we' | rule-09 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |

Second way to generate:

| Input             | Rule    | Product           |
|-------------------+---------+-------------------|
| ''                | rule-02 | A'ewe'            |
| A'ewe'            | rule-04 | BA'ewe'           |
| BA'ewe'           | rule-10 | 'one'A'ewe'       |
| 'one'A'ewe'       | rule-04 | 'one'BA'ewe'      |
| 'one'BA'ewe'      | rule-11 | 'onewar'A'ewe'    |
| 'onewar'A'ewe'    | rule-04 | 'onewar'BA'ewe'   |
| 'onewar'BA'ewe'   | rule-12 | 'onewartwo'A'ewe' |
| 'onewartwo'A'ewe' | rule-03 | 'onewartwo'B'ewe' |
| 'onewartwo'B'ewe' | rule-13 | 'onewartwoearewe' |
|-------------------+---------+-------------------|
|                   |         | 'onewartwoearewe' |
wvxvw
sumber
1
-1, karena pertanyaannya sekarang tidak masuk akal. Pertama, string bukan bahasa; string tidak ambigu, tidak ambigu, deterministik atau nondeterministik; mereka hanya string. Tata bahasa yang Anda berikan tidak menghasilkan string contoh. Saya belum memeriksa semua 180 turunan untuk melihat apakah ada duplikat, tetapi secara teori hanya itu yang perlu Anda lakukan untuk melihat apakah tata bahasanya ambigu. Sayangnya, bahasanya tidak bisa secara inheren ambigu, karena bahasanya terbatas, maka teratur, maka diterima oleh DPDA, maka deterministik.
Patrick87
@ Patrick87 eh? Di mana dikatakan bahwa string adalah bahasa? String ini adalah contoh produk, dan yakin itu mungkin untuk menghasilkan menggunakan tata bahasa yang diberikan. Apa yang membuat Anda berpikir sebaliknya? String yang dimaksud persis seperti itu, di mana dua urutan aplikasi aturan menghasilkan string yang sama, sehingga tata bahasanya ambigu, tetapi jika Anda menghapus beberapa aturan (misalnya B -> 'o', maka tidak lagi ambigu ...
wvxvw
Pertama, dapatkah Anda memberikan turunan dari string contoh menggunakan tata bahasa? Dari pertanyaan Anda sendiri: "Apakah bahasa di atas deterministik?" Anda tidak pernah menyebut bahasa, hanya string, yang dihasilkan oleh tata bahasa yang tidak terbatas, meskipun bukan yang Anda usulkan.
Patrick87
Bisakah Anda menulisnya dalam bahasa Inggris? Misalnya, "Mulai dengan S. Dengan penerapan aturan S := ..., kita dapat ..., ..."
Patrick87
@ Patrick87 Saya telah menambahkan prosedur pembuatan langkah demi langkah, dan saya menyadari saya membuat kesalahan dalam tata bahasa, yang telah saya perbaiki.
wvxvw

Jawaban:

9

PDA adalah deterministik, karenanya DPDA, jika untuk setiap konfigurasi otomaton yang dapat dijangkau, terdapat paling banyak satu transisi (yaitu, paling banyak satu konfigurasi baru dimungkinkan). Jika Anda memiliki PDA yang dapat mencapai beberapa konfigurasi yang memungkinkan dua atau lebih transisi unik, Anda tidak memiliki DPDA.

Contoh:

Q={q0,q1}Σ=Γ={Sebuah,b}SEBUAH=q0δ

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
...

Ini adalah PDA nondeterministik karena konfigurasi awal - q_0, Z0- dapat dicapai, dan ada dua transisi yang valid yang menjauh darinya jika simbol inputnya adalah a. Kapan pun PDA ini mulai mencoba memproses string yang dimulai dengan a, ada pilihan. Pilihan berarti tidak deterministik.

Pertimbangkan, sebagai gantinya, tabel transisi berikut:

q    e    s    q'   s'
--   --   --   --   --
q0   a    Z0   q1   aZ0
q0   a    Z0   q2   bZ0
q1   a    a    q0   aa
q1   a    b    q0   ab
q1   a    b    q2   aa
q2   b    a    q0   ba
q2   b    b    q0   bb
q2   b    a    q1   bb

Anda mungkin tergoda untuk mengatakan bahwa PDA ini tidak deterministik; setelah semua, ada dua transisi yang valid dari konfigurasi q1, b(a+b)*, misalnya. Namun, karena konfigurasi ini tidak dapat dijangkau oleh jalur apa pun melalui otomat, itu tidak masuk hitungan. Satu-satunya konfigurasi yang dapat dijangkau adalah subset dari q_0, (a+b)*Z0,, q1, a(a+b)*Z0dan q2, b(a+b)*Z0, dan untuk masing-masing konfigurasi ini, paling banyak satu transisi ditentukan.

CFL adalah deterministik jika itu adalah bahasa beberapa DPDA.

CFG tidak ambigu jika setiap string memiliki paling banyak satu derivasi yang valid menurut CFG. Kalau tidak, tata bahasanya ambigu. Jika Anda memiliki CFG dan Anda dapat menghasilkan dua pohon derivasi berbeda untuk beberapa string, Anda memiliki tata bahasa yang ambigu.

CFL secara inheren ambigu jika bukan bahasa CFG yang tidak ambigu.

Perhatikan yang berikut ini:

  • CFL deterministik harus menjadi bahasa beberapa DPDA.
  • Setiap CFL adalah bahasa bagi banyak PDA tanpa syarat.
  • CFL yang inheren ambigu bukan bahasa CFG yang tidak ambigu.
  • Setiap CFL adalah bahasa CFG ambigu yang tak terhingga banyaknya.
  • CFL yang inheren ambigu tidak dapat bersifat deterministik.
  • CFL nondeterministik mungkin atau mungkin tidak secara inheren ambigu.
Patrick87
sumber
1
Wiki mengatakan PDA tidak deterministik (mungkin ada versi deterministik dan non-deterministik), tetapi Anda juga bisa menghilangkan bagian pertama kalimat, itu tidak benar-benar berkontribusi pada apa yang Anda katakan: / Tapi, sekali lagi, ini mendefinisikan bahasa deterministik sebagai bahasa input dari sesuatu yang deterministik, dan sesuatu itu disebut deterministik karena ia menerima bahasa deterministik - itu seperti mengatakan "rumput berwarna hijau karena hijau adalah warna rumput". Memang benar, tetapi tidak membantu :( Tolong, contoh akan lebih berharga!
wvxvw
@wvxvw: Anda tidak membaca ini dengan benar. Dikatakan: "PDA adalah deterministik jika dan hanya jika setiap tiga negara / simbol / stacktop hanya memiliki satu negara berikutnya." Tidak ada definisi dalam definisi itu tentang bahasa apa yang diterima automaton.
Logika Pengembaraan
2
@ wvxvw Definisi PDA deterministik, atau DPDA, yang saya berikan sama sekali, bentuk, atau bentuk tidak bergantung pada definisi bahasa bebas konteks deterministik. Saya mendefinisikan DPDA hanya berdasarkan pada properti automaton. Saya kemudian mendefinisikan apa CFL deterministik dalam hal definisi DPDA. Harap baca kembali jawaban ini berdasarkan komentar-komentar ini dan Pengembaraan Logika dan cobalah untuk melihat apakah ini masuk akal. Saya akan berusaha memberikan beberapa contoh singkat.
Patrick87
q1,b(Sebuah+b)q2,b(Sebuah+b)Q={q0,...q2}karakter saat ini? Juga, apakah interpretasi saya benar? x+- satu atau lebih x, (x)*- nol atau lebih x?
wvxvw
@wvxvw Konfigurasi mengacu pada kondisi saat ini dan konten stack saat ini. x+biasanya mengacu pada "satu atau lebih dari x, sedangkan x*biasanya mengacu pada" nol atau lebih dari x; Saya dapat menggunakan xx*di tempat x+, karena ini identik.
Patrick87
7

Berikut ini contoh (dari Wikipedia):

S0S0|1S1|ε

Bahasa bebas konteks adalah deterministik jika dan hanya jika terdapat setidaknya satu otomat push-down deterministik yang menerima bahasa itu. (Mungkin juga ada banyak automata push-down non-deterministik yang menerima bahasa, dan itu masih akan menjadi bahasa deterministik.) Pada dasarnya automata push-down deterministik adalah salah satu di mana transisi mesin ditentukan secara deterministik berdasarkan keadaan saat ini, simbol input dan simbol tumpukan saat ini . Deterministikdi sini berarti bahwa tidak ada lebih dari satu transisi status untuk simbol state / input / simbol stack paling atas. Jika Anda memiliki dua atau lebih status berikutnya untuk beberapa simbol status / input / simbol stack paling atas tiga kali maka otomatnya tidak deterministik. (Anda harus "menebak" transisi mana yang harus diambil untuk memutuskan apakah otomat menerima atau tidak.)

Apa yang Knuth buktikan adalah bahwa setiap tata bahasa LR (k) memiliki otomat pushdown deterministik dan bahwa setiap deterministik pushdown automata memiliki tata bahasa LR (k). Jadi, tata bahasa LR (k) dan automata pushdown deterministik dapat menangani serangkaian bahasa yang sama. Tetapi serangkaian bahasa yang memiliki otomat pushdown deterministik yang menerimanya adalah (menurut definisi) bahasa deterministik. Argumennya tidak melingkar.

Jadi bahasa deterministik menyiratkan bahwa ada tata bahasa yang tidak ambigu. Dan kami telah menunjukkan tata bahasa yang tidak ambigu yang tidak memiliki otomat pushdown deterministik (dan dengan demikian itu adalah tata bahasa yang tidak ambigu yang menerima bahasa yang tidak deterministik.)

{Sebuahnbmcmdn|n,m>0}{Sebuahnbncmdm|n,m>0}{Sebuahnbnccdn|n>0}

Logika Pengembaraan
sumber
Bisakah Anda jelaskan, mengapa harus melihat seluruh string sebelum menentukan tengah membuat bahasa ini non-deterministik? Saya membaca penjelasan lain tentang apa itu "deterministik", dan di sana dikatakan bahwa "jika Anda tidak perlu mundur saat parsing, bahasa itu deterministik". Saya tidak melihat perlunya mundur untuk mem-parsing bahasa ini ...
wvxvw
1
Pertimbangkan string input "10011001". Automata pushdown tidak tahu berapa lama string sampai sampai akhir. Ketika Anda sampai ke 0 kedua Anda harus membuat pilihan: apakah ini string 4-karakter "1001", atau string yang lebih panjang yang terlihat seperti "100 ???? 001"? Ketika Anda sampai ke karakter kelima Anda masih tidak tahu: apakah ini string 8-karakter "10011001" atau string yang lebih panjang yang terlihat seperti "10011 ???? 11001"?
Logika Pengembaraan
1
Hal "parse the whole string" bukanlah definisi non-deterministik. Itu hanya intuisi yang ingin saya tambahkan. Baik @ Patrick87 dan saya memberi Anda definisi deterministik: dari setiap negara paling banyak ada satu negara berikutnya. Jika suatu bahasa tidak memiliki tata bahasa yang tidak ambigu, ia harus bersifat non-deterministik. Saya tidak dapat menjawab tentang contoh Anda tanpa melakukan lebih banyak pekerjaan: Anda telah menunjukkan tata bahasa yang ambigu, tetapi bukan itu yang penting, Anda perlu menunjukkan bahwa tidak ada tata bahasa yang tidak ambigu jika Anda ingin menunjukkan bahwa bahasa tersebut secara inheren ambigu.
Logika Pengembaraan
1
@wvxvw Jika Anda mencari prosedur komputasi, Anda kemungkinan kurang beruntung ... menurut en.wikipedia.org/wiki/List_of_undecidable_problems , tidak dapat dipastikan apakah CFG ambigu, apalagi apakah bahasanya secara inheren ambigu, ; itu juga tidak dapat dipastikan apakah CFG menghasilkan semua string. Mengingat hal ini, saya benar-benar ragu itu dapat diputuskan, jauh lebih efisien untuk memutuskan, apakah bahasa CFG adalah CFL deterministik.
Patrick87
1
@wvxvw Jika kebetulan Anda seberuntung itu, Anda sedang berhadapan dengan apa yang kami sebut kasus bahagia, yakni, bukan salah satu kasus yang menjadikan ini masalah yang tidak dapat diputuskan. Anda dapat mendefinisikan heuristik yang berfungsi untuk banyak kasus bahagia dan tidak meledak pada sisanya, tetapi mereka tidak akan bekerja pada semua kasus bahagia; jika mereka melakukannya, Anda akan memiliki penentu untuk masalah ini, yang menurut pendapat kami tidak mungkin.
Patrick87
5

Bahasa bebas konteks deterministik adalah bahasa yang diterima oleh beberapa otomat pushdown deterministik (bahasa bebas konteks adalah bahasa yang diterima oleh beberapa otomat pushdown non-deterministik). Dengan demikian, ini adalah properti bahasa daripada tata bahasa . Sebaliknya, ambiguitas adalah properti dari tata bahasa, sementara ambiguitas yang melekat adalah properti dari bahasa (bahasa bebas konteks secara inheren ambigu jika setiap tata bahasa bebas konteks untuk bahasa adalah ambigu).

Ada hubungan antara dua definisi: bahasa bebas konteks bebas deterministik tidak pernah secara inheren ambigu, seperti yang ditunjukkan dalam jawaban untuk pertanyaan ini .

Yuval Filmus
sumber
Maaf, itu tidak terlalu membantu. Saya sebenarnya memulai dengan DPDA, tetapi tidak pernah menjelaskan mengapa itu disebut deterministik. Ini adalah definisi yang mudah ditemukan di Wikipedia / Googling untuk makalah lain. Tapi apa properti tata bahasa / pengurai dijelaskan oleh kata "deterministik"? Dengan kata lain, apa yang harus terjadi dalam tata bahasa agar dapat disebut deterministik?
wvxvw
Maaf, jika saya terlalu banyak berkomentar. Kebingungannya adalah karena saya tidak tahu dari, katakanlah, melihat beberapa bahasa apakah itu deterministik atau tidak, dan tidak akan tahu harus mulai dari mana mengidentifikasi "determinisme" bahasa tersebut. Contoh bahasa yang bersifat deterministik dan kemudian berubah dengan cara yang membuatnya menjadi non-deterministik akan sangat membantu.
wvxvw
1
LR(k)
1
Maaf, masih belum membantu. Saya mengerti apa yang Anda katakan, tetapi itu tidak membantu saya mengenali bahasa yang deterministik dan membedakannya dari non-deterministik. Sebagai contoh: jika suatu bahasa memiliki aturan produksi yang menciptakan masalah tanda kurung yang seimbang, saya segera tahu bahwa itu tidak dapat diuraikan oleh FSM. (Karena itu akan membutuhkan tumpukan). Tetapi ketika Anda hanya menyebutkan formalisme lain, itu hanya menjadi rekursif, itu tidak membantu saya untuk memahami bagaimana bahasa itu harus berbeda dari yang lain.
wvxvw
Dengan kata lain (seperti yang Anda sebutkan dalam komentar sebelumnya), Anda ingin contoh bahasa bebas konteks dan bebas deterministik dari "sort" yang sama. Mungkin Anda harus mengajukan pertanyaan terfokus tentang hal itu.
Yuval Filmus
1

{Sebuah,b}{w(Sebuah+b)w=wR}SSebuahSSebuah|bSb|Sebuah|b|ϵSebuahbSebuahbSebuahb

PMar
sumber
1

Definisi

  1. Sebuah pushdown akseptor deterministik (DPDA) adalah otomat pushdown yang tidak pernah memiliki pilihan dalam perubahan.
  2. DPDA dan NPDA tidak setara.
  3. Sebuah CFG adalah non deterministik IFF ada setidaknya dua produksi dengan awalan terminal yang sama di sisi kanan dari mereka.
  4. Sebuah CFG adalah ambigu IFF terdapat beberapa w ∈ L (G) yang memiliki setidaknya dua pohon derivasi yang berbeda. Dengan demikian, ia memiliki dua atau lebih derivasi paling kiri atau paling kanan sesuai dengan dua pohon derivasi yang berbeda.
  5. Sebuah CFG adalah ambigu IFF setiap string yang memiliki paling banyak satu derivasi sah menurut CFG tersebut. Kalau tidak, tata bahasanya ambigu.
  6. Sebuah CFL adalah inheren ambigu IFF itu bukan bahasa setiap CFG ambigu. Itu tidak dapat memiliki DPDA.
    Jika setiap tata bahasa yang menghasilkan CFL adalah ambigu, maka CFL disebut inheren ambigu . Jadi itu bukan bahasa setiap CFGs ambigu.

Fakta

  1. Setiap CFL adalah bahasa bagi banyak PDA tanpa syarat.
  2. Setiap CFL adalah bahasa CFG ambigu yang tak terhingga banyaknya .
  3. CFL yang diterima oleh beberapa DPDA pada dasarnya tidak ambigu. (Ada setidaknya satu CFG jelas untuk itu.)
  4. CFL yang diterima oleh NDPDA mungkin secara inheren bersifat ambigu karena ada beberapa DPDA (atau CFG yang tidak ambigu) untuknya.
  5. CFL yang dihasilkan oleh CFG ambigu mungkin atau mungkin tidak secara ambigu ambigu karena mungkin ada beberapa CFG (atau DPDA) yang ambigu untuknya.
  6. CFL yang dihasilkan oleh setidaknya satu CFG yang tidak ambigu tidak secara inheren ambigu. (Ada beberapa DPDA untuk itu.)
  7. Tata bahasa yang tidak deterministik mungkin atau mungkin tidak ambigu.

Jawab pertanyaan Anda (hubungan antara determinisme dan ambiguitas)

  1. Ambiguitas (Non) berlaku terutama untuk tata bahasa (di sini CFG). (Non) determinisme berlaku untuk tata bahasa dan otomat (di sini PDA).

    Jika Anda menginginkan perbedaan logis, Anda dapat melihat empat poin terakhir di bagian fakta ketika mereka mencoba menghubungkan ambiguitas dan determinisme. Di sini saya mengulanginya lagi:

  2. CFL yang diterima oleh beberapa PDA deterministik pada dasarnya tidak ambigu . (Ada setidaknya satu CFG jelas untuk itu.)

  3. CFL yang diterima oleh PDA non deterministik mungkin atau mungkin tidak secara inheren ambigu karena mungkin ada beberapa DPDA (atau CFG tidak ambigu ) untuk itu.
  4. CFL yang dihasilkan oleh CFG ambigu mungkin atau mungkin tidak secara ambigu ambigu karena mungkin ada beberapa CFG yang tidak ambigu (atau PDA deterministik ) untuknya.
  5. Sebuah CFL yang dihasilkan oleh setidaknya satu ambigu CFG tidak inheren ambigu . (Ada beberapa DPDA untuk itu.)
  6. Sebuah non deterministik tata bahasa mungkin atau mungkin tidak ambigu .

PS:

  1. Jawaban yang diterima menggunakan baris seperti "CFL bersifat deterministik", "CFL deterministik", "CFL tidak dapat bersifat deterministik", "CFL yang tidak deterministik". Saya kira kata sifat "deterministik" dan "ambigu" tidak berlaku untuk CFL, tetapi untuk PDA dan CFG. (Meskipun kata sifat "secara inheren ambigu" berlaku untuk CFL) Meskipun saya tidak ingin mengkritik jawaban asli, karena saya sendiri belajar penting poin dari itu. (Sebenarnya saya benar-benar menyalin beberapa baris dari jawaban itu.) Tetapi saya masih merasa itu harus dibuat lebih benar. Jadi saya mencoba untuk meletakkan barang-barang lebih jelas di sini dalam dua bagian, definisi dan fakta (saya mungkin membuatnya terlalu panjang dan panjang). Saya kira saya seharusnya mengedit jawaban asli, tetapi kemudian akan melibatkan menghapus banyak poin yang menggunakan baris di atas. Dan saya tidak tahu apakah ini akan membuatnya menjadi edit yang valid karena melibatkan penulisan ulang lengkap.
  2. Perhatikan bahwa saya telah memasukkan kata-kata kuantitatif dalam huruf miring tebal untuk menyoroti perbedaan komparatif dalam berbagai definisi dan fakta. Istilah definisi hanya dicetak tebal .
  3. Beberapa poin yang saya buat sendiri, jadi saya perlu konfirmasi dari seseorang yang berpengetahuan di sini tentang kebenaran setiap poin.
Maha
sumber
PS 1 salah: ada definisi standar untuk CFL deterministik / ambigu, yaitu, mereka didefinisikan sebagai yang semua CFG deterministik / ambigu.
reinierpost
baru sadar fakta 7 salah. Poin 6 dari daftar terakhir kedua adalah sama dan salah.
Maha
Memang ... determinisme tidak memiliki ambiguitas pada titik mana pun selama parsing, jadi itu lebih kuat daripada ambiguitas (yaitu ambiguitas bahkan setelah parsing telah selesai).
reinierpost