Bir NFA tarafından kabul edilen dilin, başka biri tarafından kabul edilen dilin bir üst kümesi olup olmadığına karar vermek için etkili bir algoritma var mı?

iki deterministik olmayan sonlu otomata Verilen M1 ve M2, M1 tarafından kabul dil M2 tarafından kabul dilinin bir üst olup olmadığını belirlemek için verimli bir algoritma var mı?Bir NFA tarafından kabul edilen dilin, başka biri tarafından kabul edilen dilin bir üst kümesi olup olmadığına karar vermek için etkili bir algoritma var mı?

kaynak

2012-02-25 Daniel Trebbien

P = NP olmadığı sürece. Böyle bir algoritma varsa, iki NFA'nın izomorfik olup olmadığına kısaca karar verebilirsiniz (A'nın A ve B'nin üst kümesi A olup olmadığını kontrol edin), yani known NP-hard problem. Daha fazla bilgi için, read this paper. Karmaşıklık sonuçlarının güzel cesaret kırıcı bir tablosuna sahiptir.

kaynak

2012-02-26 03:15:25 Mikola

Acaba NFA izomorfizmi için bir başka NP tam probleminden bir azalma olduğunu biliyor musunuz? – hugomg

@missigno: Redüksiyonları biraz daha dikkatli açıklayan bir makaleye bağlantı ekledim. – Mikola

Mikola, cevabınız doğru ama sizin ifadeleriniz yanlış: izomorfik "eşit şekil" anlamına gelir, iki otomata isomorfiktir, yani kendi devletleri arasında 1-1 haritalama vardır, bla bla. Burada ilgisi olmayan iki otomatik isim, izomorfik olmaksızın aynı dili kabul edebilir. (Grafik isomorphisminin de NP-Hard olduğunu kontrol eden karmaşaya katkıda bulunur) Eğer cevabınızı "iki NFA'nın aynı dili kabul edip etmediği" şeklinde düzenlerseniz, "iki NFA'nın izomorfik olup olmadığını" söylerseniz hepsi iyi olacaktır. –

Bir NFA tarafından kabul edilen dilin, başka biri tarafından kabul edilen dilin bir üst kümesi olup olmadığına karar vermek için etkili bir algoritma var mı?

cevap

İlgili konular