Please enable JavaScript.
Coggle requires JavaScript to display documents.
Proprietà positive dei CFL, Proprietà negative dei CFL - Coggle Diagram
Proprietà positive dei CFL
I CFL sono chiusi rispetto a
Unione
Se L_1 e L_2 sono CFL
Allora anche $$L_1 \cup L_2$$ è CFL
Si crea un nuovo simbolo iniziale
Che può generare il simbolo iniziale della prima grammatica
Oppure quello della seconda
$$S \rightarrow S_1 | S_2$$
Concatenazione
Se L_1 e L_2 sono CFL
Allora anche $$L_1 \cdot L_2$$ è CFL
Si crea un nuovo simbolo iniziale
Che genera prima una parola del linguaggio
E poi una del secondo
$$S \rightarrow S_1S_2$$
Stella di Kleene
Se L è CFL
Si utilizza una nuova variabile iniziale ricorsiva
Che può ripetere il linguaggio quante volte vuole
Oppure fermarsi con $$\lambda$$
$$S_1 \rightarrow SS_1 | \lambda$$
Proprietà negative dei CFL
I CFL non sono chiusi rispetto a
Intersezione
Due linguaggi CFL se li interseco
Non è detto che il risultato sia ancora CFL
Complemento
Il complemento di un CFL
Non è necessariamente un CFL