[Introduzione alla teoria della computazione] Esercizio 1.14

[FeddyLix17]

1. Mostrare che se $\Large M$ è un $\Large DFA$ che riconosce il linguaggio $\Large B$, scambiare gli stati accettanti con gli stati non accettanti in $\Large M$ definisce un nuovo $\Large DFA$ che riconosce il complemento di $\Large B$.
   
   Concludere che la classe dei linguaggi regolari è chiusa rispetto al complemento.


2. Mostrare con un esempio che se $\Large M$ è un $\Large NFA$ che riconosce il linguaggio $\Large C$, scambiare gli stati accettanti con gli stati non accettanti in $\Large M$ non necessariamente definisce un nuovo $\Large NFA$ che riconosce il complemento di $\Large C$.
   
   La classe dei linguaggi riconosciuti da $\Large NFA$ è chiusa rispetto al complemento? Giustifica la tua risposta.