Kertas dengan bukti itu

8

Slide kuliah ini membuat sketsa bukti ituL={anbnn0}{anb2nn0} tidak dapat diterima oleh Deterministic Pushdown Automaton. Sayangnya, slide tidak memberikan referensi ke mana bukti itu berasal.

Saya bertanya-tanya, apakah ada yang tahu makalah akademis atau buku teks yang memberikan bukti penuh? Saya ingin sekali mengutipnya, tetapi saya belum dapat menemukannya.

Ya ampun
sumber
Sebagai catatan: slide mengikuti argumen yang sama seperti yang saya gunakan dalam pertanyaan terkait tentang Pumping Lemma's untuk CFL deterministik. (Ini tentu saja argumen yang tidak memompa.)
Hendrik

Jawaban:

6

Hasilnya dibuktikan dalam Ginsburg dan Greibach, konteks bebas bahasa Deterministic , Inform. Kontrol 9 (6), 620-648, 1966 , Teorema 4.1 pada halaman 24 (643). Namun, buktinya terlihat agak berbeda.

Yuval Filmus
sumber
Luar biasa! Terima kasih banyak! Saya telah melihat referensi pada makalah itu tetapi kesulitan menemukan salinan PDF.
jmite
1
Karena penasaran, bagaimana Anda menemukan itu? Apakah Anda tahu begitu saja kertas apa yang ada di dalamnya, atau apakah Anda entah bagaimana mencarinya? Saya mencoba untuk mengembangkan kemampuan kertas-cari saya ...
jmite
1
Saya mencari "konteks deterministik gratis" di Google dan itu adalah salah satu hasil teratas. Abstraknya tidak terlalu menjanjikan, tetapi dalam pendahuluan mereka menyebutkan hasil ini.
Yuval Filmus