Tutti gli articoli ( esempio ) Ho letto fino ad ora su regolare le espressioni e le NFA spiegano tre operazioni:
Nessuno parla della negazione. La negazione non è regolare?
Aggiornamento:
@RemcoGerlich Che cosa significa "scambiare gli stati". Puoi spiegarlo con la chiusura di Kleene?
Come apparirebbe la chiusura di Kleene con stati scambiati?
Sì; primo, ogni automa finito non deterministico può essere convertito in un automa finito deterministico che accetta lo stesso linguaggio.
Ora, solo rende tutti gli stati accettanti non accettati e viceversa : questo nuovo DFA accetta una stringa esattamente quando il DFA originale non lo fa, quindi la sua lingua è il complemento della lingua originale.
Una panoramica sulla mia domanda.
Il motivo per cui gli articoli che spiegano la conversione dell'espressione regolare in NFA non spiegano che la negazione sembra essere un problema particolare degli NFA, il che rende complicata la negazione. Come spiegato da RemcoGerlich, l'NFA deve essere convertito in un DFA per negarlo. Ma normalmente l'espressione regolare viene prima convertita in un NFA e successivamente in un DFA.
Ho trovato un articolo che descrive come evitare la creazione di un NFA. Invece l'espressione regolare viene convertita direttamente in un DFA mediante l'uso di derivati: "Derivati di espressione regolare rivisti ". E questo approccio rende abbastanza facile implementare anche la negazione.
Leggi altre domande sui tag regular-expressions