[linguaggi regolari, grammatiche] Tipo del linguaggio - grammatica

Messaggioda ilkosta » 19/02/2020, 18:21

Buongiorno,

considerando la famiglia di insiemi S(i) che al variare dell'indice `i` sono costituiti da stringhe con l'i-esimo simbolo `o`, occorre stabilire il tipo del linguaggio dato dall'unione degli insiemi in cui `i` e' un quadrato perfetto in S(i).

Sul testo che sto consultando la soluzione parte subito dal dire che

"
Notiamo che la condizione di essere un quadrato perfetto non è, intuitivamente, una
condizione che rappresenta un fatto regolare, in quanto i quadrati perfetti crescono
in modo esponenziale, è dunque difficile che esistano un automa o una grammatica
capaci di riconoscerlo, per questo dimostriamo direttamente che il linguaggio non è
CF
"

Questo m'ha spiazzato e faccio ancora fatica a "digerirlo": nella mia ingenuita', leggendo il testo dell'esercizio, avevo subito pensato che l'unione e' chiusa rispetto ai linguaggi regolari. Quindi se posso costruire un automa che accetti le stringhe che presentano `o` nella i-esima posizione data in cui `i` e' un quadrato perfetto... allora il risultato dell'unione e' sicuramente un linguaggio regolare.
Non capisco perche' improvvisamente l'unione di tanti (ok infiniti) linguaggi regolari, non sia piu' regolare.

Ringrazio in anticipo chiunque volesse aiutarmi
ilkosta
Starting Member
Starting Member
 
Messaggio: 1 di 2
Iscritto il: 19/02/2020, 16:04

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite