Fino ad ora abbiamo visto come costruire automi per riconoscere linguaggi semplici, infatti bastava leggere prima dei caratteri in un determinato numero, e poi altri caratteri. Abbiamo sempre trattato linguaggi con dei vincoli anche sulla struttura della parola, come ad esempio 1^2k 0*.

In questa sezione, dedicata ad esercizi Difficili, le cose non saranno così scontate come in precedenza.

Per farvi capire di cosa sto parlando, proviamo a confrontare questi due linguaggi:

• L = {0^2K, 1^2k+1 | K ∈ N}
• L = {#0 (w) = 2k, #1 (w) = 2k+1 | K ∈ N}

Quali sono le differenze? Entrambi hanno le stesse condizioni, ovvero che il numero di zeri devono essere pari ed il numero di 1 devono essere dispari.

Ma…il primo linguaggio ci dice che gli zeri vengono prima degli 1, mentre nel secondo quest’ ordine non viene definito.

Per farti capire ancora meglio quello che sto dicendo esaminiamo le parole dei due linguaggi:

L1 = {001, 00111, 0011111, 00001, 0000111, 000011111…}

L2 = {010, 01011, 1101101, 00100, 0101010, 010101011…}

Come puoi intuire le cose si complicano esponenzialmente.

Prendiamo come riferimento il linguaggio: L = {#0 (w) = 2k, #1 (w) = 2k+1 | K ∈ N}.

Devi sapere che c’è una proprietà molto importante dei linguaggi regolari, la proprietà di chiusura. Questa proprietà, tra le tante cose, ci dice che la classe dei linguaggi regolari è chiusa rispetto all’ unione ed all’ intersezione. Ma cosa vuol dire? Significa semplicemente che un linguaggio (regolare) può essere espresso tramite unione o intersezione di 2 o più linguaggi (regolari). In parole povere:

• L1 = L2 U L3;
• L1 = L2 U L3 U (L4 ∩ L5);
• L1 = L2 ∩ L3 U (L4 U L5).

Quindi possiamo semplificarci la vita scomponendo il linguaggio iniziale in due sottolinguaggi più semplici da analizzare.

Scomposizione in sottolinguaggi

Come facciamo a scomporre un linguaggio in più sottolinguaggi?

Semplicemente basta separare le condizioni. Nel nostro caso abbiamo le seguenti condizioni:

• #0 (w) = 2k;
• #0 (w) = 2k+1.

Costruiamo due linguaggi distinti nel seguente modo:

• L1 = {#0 (w) = 2k | K ∈ N}
• L2 = {#1 (w) = 2k+1 | K ∈ N}

Il linguaggio iniziale sarà dato dall’ intersezione dei due linguaggi trovati:

L = L1  ∩ L2

Costruire l’ Automa

Per costruire l’ automa del linguaggio iniziale possiamo inizialmente costruire l’ automa dei singoli linguaggi, e poi effettuare l’ intersezione.

Proviamo a costruire l’ automa del primo linguaggio:

Costruiamo ora l’ automa del secondo linguaggio:

Volendo, l’ esercizio sarebbe finito qui. Non c’è bisogno di tirar fuori l’ automa del linguaggio iniziale, anche potrebbe uscire di dimensioni cosmiche. In questo caso l’ automa finale sarebbe il seguente:

Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Automi.

Alla prossima!