Può una grammatica generare tante parole quanti i reali?

[lorenzo902]

In un esercizio veniva chiesto: "Può una grammatica qualsiasi (quindi regular,context sensitive,context free o unrestricted) generare tante parole quanti sono i numeri reali?". Il professore ci ha anticipato che la risposta è no, chiedendoci di dimostrare il perché ma non so da dove cominciare...

Avete qualche idea?

Grazie

[claudio862]

Chiediti se potrebbe generare tante parole quanti sono i numeri interi. In caso positivo, chiediti qual è la differenza con i reali.
Altro suggerimento:

Per generare una parola devi applicare una sequenza di sostituzioni dal simbolo iniziale a quelli terminali.

[lorenzo902]

"claudio86":Chiediti se potrebbe generare tante parole quanti sono i numeri interi. In caso positivo, chiediti qual è la differenza con i reali.
Altro suggerimento:

Per generare una parola devi applicare una sequenza di sostituzioni dal simbolo iniziale a quelli terminali.

Grazie della risposta ma ancora non mi tornano le cose purtroppo
Sicuramente posso costruire una grammatica che mi genera tutti i numeri naturali (costruendo prima l'automa) o anche gli interi. In questo caso, dato che genera tutti i naturali, può generare tante parole quanti i naturali.
Ma, in modo simile, non potrei costruire anche un automa che riconosce i reali e genera tante parole quanti i reali ?
Dove sbaglio ?
Grazie

[apatriarca]

La risposta alla tua domanda è ovviamente no. Non puoi generare un automa che riconosce un numero reale. Come dovrebbe fare a riconoscere ad esempio \(\pi\)? La ragione per cui non puoi farlo è esattamente quella per cui la risposta alla domanda iniziale era no.. Come altro suggerimento posso darti questo:

Puoi generare una grammatica per i numeri razionali, che cosa cambia rispetto ai numeri reali?

[claudio862]

Ogni simbolo terminale viene generato da una sequenza finita di regole.
Quindi puoi dare un indice univoco ad ogni simbolo terminale *.
Quindi ad ogni simbolo terminale corrisponde un numero naturale.
Quindi, dato che la cardinalità dei naturali \(\displaystyle \aleph_0 \lneqq \aleph_1 \) la cardinalità dei reali, non puoi generare i reali, sono troppi.

* Puoi farlo in molti modi, sostanzialmente è una generalizzazione della procedura di diagonalizzazione di Cantor. Ad esempio, numeri le regole (con un po' d'attenzione) e concateni quelle usate.
Applico le regole 1, 23, 5 => l'indice è 012305

[lorenzo902]

Grazie