Lezione del 4 Ottobre 2011
Pumping Lemma abababb
y = a w = baba z = b
L(A)=a(ba)nbb
Non è per forza univoco, si poteva prendere ab.
Con gli automi si può scrivere un linguaggio di programmazione ma meno potente del solito, ci interessa un linguaggio di 0 programmi corretti e con un solo numero finito di programmi?
Esempio A = {a;b}
anbn per n > 0
Non posso permutare a e b e devo avere lo stesso numero di a e di b. E’ un linguaggio a parentesi che accetta una struttura gerarchica semplce.
E’ un linguaggio che non è accettato da alcun automa a stati finiti.
Intersezione ed unione di automi di turing.
Faccio il complemento sfruttando De Morgan Filosofia del complemento
