OliForum Matematico

Questo è per chi sa un pochino di teoria degli automi (poco più delle definizioni di automa e di linguaggio riconosciuto da un automa).

Si chiamano regolari tutti i linguaggi riconosciuti da un automa (automa si intende a stati finiti). Se $ L $ è un linguaggio definiamo $ HALF(L) $ come il linguaggio ottenuto dividendo a metà esatta le stringhe di lunghezza pari in $ L $ e prendendo la seconda metà, cioè $ HALF(L) = \{ w | \exists s. |s| = |w|, sw \in L \} $. Dimostrare che se $ L $ è regolare anche $ HALF(L) $ è regolare.

Perchè L sia regolare, deve esserci un automa deterministico A (con funzione di transizione d) che lo calcola.
Se una stringa di lunghezza 2n è in L, durante la verifica deve passare al passo n su uno stato s.
Conoscendo s, si può costruire una nuova macchina deterministica dove i nuovi stati sono coppie di stati di A, le transizioni sono quelle naturali (cioè da (a,b) si passa in (d(a), d(b)), gli stati iniziali sono quelli del tipo (s,i) con i stato iniziale, gli stati finali sono quelli del tipo (f,s) con f stato finale.
Poichè s non è fissato, si costruisce una macchina di questo tipo per ogni stato di A, e si mettono in parallelo (cioè si mette all'inizio una epsilon-transizione che parte dallo stato iniziale verso gli stati iniziali di ciascuna sottomacchina). Si ottiene quindi una macchina non deterministica che riconosce HALF(L) e quindi HALF(L) è regolare.