5
Dati due automa a stati finiti non deterministico M1 e M2, c'è un algoritmo efficiente per determinare se la lingua accettata M1 è un sovrainsieme del linguaggio accettato da M2?Esiste un algoritmo efficiente per decidere se la lingua accettata da una NFA è un superset della lingua accettata da un'altra?
Mi chiedo, sai di una riduzione da un altro problema NP completo all'isomorfismo NFA? – hugomg
@missigno: ho aggiunto un collegamento a un foglio spiegando le riduzioni un po 'più attentamente. – Mikola
Mikola, la tua risposta è corretta ma la tua formulazione è sbagliata: isomorfo significa "di uguale forma", due automi sono isomorfici se esiste una mappatura 1-1 tra i loro stati, tale che bla bla. Che non è rilevante qui, due automi possono accettare la stessa lingua senza essere isomorfi. (Si aggiunge alla confusione che il controllo dell'isomorfismo del grafico sia anche NP-Hard) Se modifichi la tua risposta come "se due NFA accettano la stessa lingua" invece di "se due NFA fossero isomorfe" tutto andrà bene. –