half(L) è regolare

Calcolabilità, modelli di calcolo, complessità, linguaggi formali.

half(L) è regolare

Messaggioda marco il mer 19 set 2012, 19:57

Classico. Dato L regolare, dimostrare che anche {\rm half}(L) = \{  x \mid xy \in L \land |x|=|y| \} è regolare.
The first rule of first order logic is you can't talk about first order logic
marco
 
Messaggi: 26
Iscritto il: mer 2 lug 2008, 16:27

Torna a Fondamenti dell'Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite