Linguaggio della macchina

<aside> 💡 Se $A$ è l’insieme di tutte le stringhe che la macchina accetta, diciamo che $A$ è il linguaggio della macchina $M$

</aside>

• scriviamo $L(M) =A$
• diciamo che $M$ riconosce (o accetta) ****$A$

Ogni macchina riconosce sempre e soltanto un linguaggio

Se la macchina non accetta alcuna stringa, riconosce ancora un linguaggio → il linguaggio vuoto

• $L(M)= \empty$

Linguaggio regolare

<aside> 💡 Un linguaggio è chiamato linguaggio regolare se esiste un automa finito che lo riconosce

</aside>

Osservazioni

• un DFA accetta $\epsilon$ se e solo se il suo stato iniziale è accettante
• ogni DFA tale che tutti gli stati sono accettanti riconosce il linguaggio $\sum^*$
• ogni DFA che non ha stati accettanti rifiuta tutte le stringhe: riconosce il linguaggio $\empty$