Dimostrare che il complemento di un linguaggio regolare è regolare

Ciao a tutti!
Come posso fare questa dimostrazione?
"Dimostrare che il complemento di un linguaggio regolare è regolare." È dell'appello del 6 gennaio 2011

Comments

  • Ho controllato le dispense ma la dimostrazione è "lasciata al lettore".
    A grandi linee credo basti fare così:
    Prendiamo l'automa A che riconosce il nostro linguaggio regolare e lo trasformiamo in uno nuovo A' in cui tutti gli stati finali di A diventano non finali e viceversa. Bisogna considerare anche gli stati pozzo che solitamente vengono eliminati perchè in questo caso diventano tutti stati finali di accettazione.
  • dima91dima91 Posts: 11
    Ho trovato questa dimostrazione:
    "Per ipotesi L è accettato da un automa a stati finiti M= (Q, A, t, q0, F). L'insieme delle parole appartenenti a L complementare è tale che per ogni y appartenente ad A*, t(q0, y) non appartiene ad F e quindi tale che t(q0, y) appartiene a Q-F. Ne segue che L complementare è accettato dall'automa M'= (Q,A, t, q0, Q-F) e quindi è un linguaggio regolare."
    Dovrebbe andare bene.
  • MindFlyerMindFlyer Posts: 436
    Sì, se accetti il teorema di caratterizzazione dei linguaggi regolari come linguaggi riconosciuti da automi a stati finiti, in effetti è banale. Più interessante è farlo direttamente con le espressioni regolari.

    Non so chi tenga questo corso, ma se è Degano dovete aspettarvi domande banali e trolleggi vari allo scritto. Tipo insiemi definiti in modi complicati che a guardar bene sono vuoti, etc.
  • dima91dima91 Posts: 11
    No no, c'è il Turini all'esame
  • Da come ho capito io, si dice che preso L come insieme dei linguaggi regolari si considera il sul complementare con gli stati terminali presi come non terminali e viceversa.. E quindi anche L complementare termina ed é regolare
Sign In or Register to comment.