Linguaggi context free e proprietà

[grandpri]

Salve a tutti!

ho un problema che mi toglie il sonno da alcuni giorni:

Qualcuno riuscirebbe a descrivere un algoritmo/teorema/qualcosa che mi dice se un linguaggio context free sia finito oppure infinito?
Ed esiste qualcosa del genere anche per i linguaggi regolari?

[linuxloverstaff]

Puoi vedere con il pumping lemma che un linguaggio regolare riconosce un isieme infinito di stringhe di lunghezza finita.

[grandpri]

ma come faccio a capire, dato un linguaggio regolare oppure uno libero dal contesto, se il linguaggio e finito o infinito?

[linuxloverstaff]

"grandpri":ma come faccio a capire, dato un linguaggio regolare oppure uno libero dal contesto, se il linguaggio e finito o infinito?

Io considero un linguaggio infinito se accetta un insieme infinito di stringhe.
Siccome il pumping lemma dice che un linguaggio è regolare se accezza una stringa x.(y^k).z dove y è ripetuta K volte (k>=0), allora so che un linguaggio regolare accetta infinite stringhe.

Per i context free...io ricordo meglio le grammatiche context free rispetto ai linguaggi, ma tanto sono modi diversi di dire una stessa cosa.

Supponiamo che la mia grammatica generi la stringa

something.ABABABA.something

Ho indicato con something il contesto, con ABABABA la stringa generata dalla grammatica G (e quindi accettata dal linguaggio Lg). Bene, questa è completamente indipendente da something, quindi per me anche questo secondo tipo di linguaggi riconosce infinite stringhe.

Se un linguaggio libero da contesto non riconoscesse infinite stringhe, allora non sarebbe più libero dal contesto...pensa al compilatore di un software in C. (Purtroppo su questo secondo tipo di linguaggi ho meno ricordi)