Linguaggio non regolare

[francesco1b]

Salve a tutti, la mia domanda è la seguente: dato un linguaggio F regolare , un suo sottoinsieme finito può essere non regolare ?in caso positivo potete farmi un esempio?
Grazie!

[apatriarca]

Penso che la risposta sia che non può esistere: ogni insieme finito di stringhe su un qualche alfabeto è regolare se non sbaglio.

[MarcoChampion1]

Ciao Francesco, per definizione ogni linguaggio FINITO è regolare. Per cui da un linguaggio regolare F ogni suo sottoinsieme FINITO sarà regolare.
Invece, dato un linguaggio regolare F, non è detto che un QUALSIASI suo sottoinsieme sia regolare: ad esempio se S = {a,b} è il nostro alfabeto, l'insieme S* di tutte le stringhe possibili su S è un linguaggio regolare ma il suo sottoinsieme D = { $ a^nb^n $ } non è regolare!