[LF]Star di Kleene
Salve,
avrei un piccolo dubbio da chiarire di Linguaggi Formali.
Nel testo ho questa frase sulla "Star di Kleen" e la "chiusura positiva":
"Finally, the positive closure, denoted $L^+$, is the same as the Kleene closure, but without the term $L^0$. That is, $epsilon$ will not be in $L^+$ unless it is in $L$ itself"
Cioè se ho un alfabeto
$L={a,b,c}$
$L^\**$ è l'insieme di stringhe di lunghezza $>=0$.
$L^+$ è l'insieme di stringhe di lunghezza $>0$
Ma l'ultima frase si riferisce nel caso se:
$L={epsilon,a,b,c}$
cioè:
$L^+$ in questo caso può essere di lunghezza $0$, solo perchè l'alfabeto contiene il valore di stringa nulla????
Mi serve una smentita o meno.
Altro dubbio sulle grammatiche context-free:
ma derivazione sinistra/destra è sinonimo di ricorsione sinistra/destra, o dipende dal contesto?
Ringrazio chi aiuta
avrei un piccolo dubbio da chiarire di Linguaggi Formali.
Nel testo ho questa frase sulla "Star di Kleen" e la "chiusura positiva":
"Finally, the positive closure, denoted $L^+$, is the same as the Kleene closure, but without the term $L^0$. That is, $epsilon$ will not be in $L^+$ unless it is in $L$ itself"
Cioè se ho un alfabeto
$L={a,b,c}$
$L^\**$ è l'insieme di stringhe di lunghezza $>=0$.
$L^+$ è l'insieme di stringhe di lunghezza $>0$
Ma l'ultima frase si riferisce nel caso se:
$L={epsilon,a,b,c}$
cioè:
$L^+$ in questo caso può essere di lunghezza $0$, solo perchè l'alfabeto contiene il valore di stringa nulla????
Mi serve una smentita o meno.
Altro dubbio sulle grammatiche context-free:
ma derivazione sinistra/destra è sinonimo di ricorsione sinistra/destra, o dipende dal contesto?
Ringrazio chi aiuta
Risposte
Formalmente è differente: se il tuo $L$ è un linguaggio allora $L^\**$ e $L^+$ sono una cosa, mentre se hai un alfabeto $Sigma$, con $Sigma^\**$ si indica il linguaggio di tutte le stringhe generabili con i simboli di tale alfabeto; $Sigma$ è un alfabeto, $Sigma^\**$ è un linguaggio.
L'incomprensione nasce da questo, secondo me: con $epsilon$ o $lambda$ in genere si indica la stringa vuota, che è parte di un linguaggio e non di un alfabeto.
Esempio, se hai un linguaggio infinito $L={a^x b^y | x>y>0}$ allora avrai capito cosa sono $L^0$, $L^1$, $L^2$ e in generale $L^\**$ e $L^+$.
Prova a fare lo stesso con il linguaggio $L={epsilon}uu{a^x b^y | x>y>0}$
---
Derivazione e ricorsione non sono sinonimi, come la parola suggerisce. A parole - ma dovrebbe essere chiaro dai contesti nei quali trovi i termini, non credo ti sarà difficile comprendere la differenza - la ricorsione è una derivazione che "torna su se stessa". Se per esempio puoi derivare una certa stringa da una grammatica, avrai trovato la sua derivazione; se puoi derivare un certo simbolo non terminale a partire dallo stesso simbolo, avrai trovato una ricorsione.
L'incomprensione nasce da questo, secondo me: con $epsilon$ o $lambda$ in genere si indica la stringa vuota, che è parte di un linguaggio e non di un alfabeto.
Esempio, se hai un linguaggio infinito $L={a^x b^y | x>y>0}$ allora avrai capito cosa sono $L^0$, $L^1$, $L^2$ e in generale $L^\**$ e $L^+$.
Prova a fare lo stesso con il linguaggio $L={epsilon}uu{a^x b^y | x>y>0}$
---
Derivazione e ricorsione non sono sinonimi, come la parola suggerisce. A parole - ma dovrebbe essere chiaro dai contesti nei quali trovi i termini, non credo ti sarà difficile comprendere la differenza - la ricorsione è una derivazione che "torna su se stessa". Se per esempio puoi derivare una certa stringa da una grammatica, avrai trovato la sua derivazione; se puoi derivare un certo simbolo non terminale a partire dallo stesso simbolo, avrai trovato una ricorsione.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo