Chiusura sulle lingue regolari

Question

a) Let $ L $ Sii una lingua normale.Secondo il teorema c'è un DFA che accetta la lingua.

Descrivi poco come modificare il DFA in NFA che accetta $ l ^ r $ , dove r è inverso.

Non è necessario scrivere come costruire formalmente o prova o correttezza.

b) True o Falso: se $ l $ non è normale allora $ l ^ r $ non è normale

La mia soluzione:

a) Prima di tutto perché vogliamo invertire lo stato di accettazione sarebbe diventato l'inizio e gli stati di rifiuto diventeranno accettando, cambia anche la direzione dei bordi al lato opposto. Ma quando si tratta di cambiarlo in NFA sono un po 'bloccato.

b) Penso che sia vero poiché non ha importanza se invertita se è regolare allora, naturalmente, naturalmente, Classe MAWS="container matematica"> $ l ^ r $ Igienico

è questa la via per A e B?

Answer 1

a)

.

Prima di tutto perché vogliamo invertire lo stato di accettazione diventerà l'inizio e gli stati di rifiuto diventerà accettando, cambia anche la direzione dei bordi per il lato opposto.

Sei quasi lì. Cosa succede se hai più stati accettati nell'originale DFA? Ecco dove hai bisogno di funzionalità NFA per convertirle.

Ecco uno spoiler nel caso in cui desideri controllare la risposta: Progettare un DFA e il contrario di IT su ComputersCience.se .

B)

La tua risposta è vera anche se potresti voler esplodere un po 'più attentamente. Vogliamo dimostrare "se $ l $ non è regolare, $ l ^ r $ non è normale" . Quindi lascia che $ l $ non essere regolare. Se $ l ^ r $ erano regolari, quindi erano $ (l ^ r) ^ r= l $ , che è una contraddizione. Quindi, $ l ^ r $ non è normale.