En küçük dilbilgisi sorunu - Smallest grammar problem

Gelen veri sıkıştırma ve teorisi biçimsel dillerin , en küçük gramer sorunu en küçük bulma sorunudur bağlam serbest dilbilgisi belirli bir üretir dize karakter (ancak başka dize). Bir gramer büyüklüğü üretim kurallarının sağ tarafındaki semboller sayısı olarak bazı yazarlar tarafından tanımlanır. Diğerleri de buna kuralları sayısını ekleyin. Sorunu (karar versiyonu) olan NP-tam . Belirli bir dize üreten en küçük bağlam serbest dilbilgisi her zaman olduğu doğrusal dilbilgisi olmadan yararsız kurallara .

Ayrıca bakınız

• Dilbilgisi tabanlı kod
• Kolmogorov karmaşıklığı
• Kayıpsız veri sıkıştırma
• Doğrusal dilbilgisi

Referanslar

• Charikar, Musa; Lehman Eric; Liu, Ding; Panigrahy Rina; Prabhakaran Manoj; Rasala Nisan; Sahai Amit; Shelat Abhi (2002). "En küçük Dilbilgisi takribi: Kolmogorov karmaşıklığı Doğal Modellerde". Bilgi işlem (STOC 2002), Montreal, Quebec, Kanada, Mayıs 19-21, 2002 teorisi üzerine otuz dördüncü yıllık ACM Sempozyumun Tutanakları (PDF) . New York, NY: ACM basın. s. 792-801. doi : 10,1145 / 509.907,510021 . ISBN  1-581-13495-9 . ZBL  1192.68397 .

Bu algoritmalar veya veri yapıları lı makale bir taslaktır . Sen Vikipedi'ye katkıda bulunabilirsiniz genişletmeden . v t e