Context free

[starsuper]

Dopo lo studio delle esporessioni regolari mi trovo alle prese con grammatiche context free. Non riesco a capire o meglio a praticizzare cio che ho letto, ad esempio S-->aSa, cosa siginifica? Capisco che si basa su regole di derivazione, ma non capisco, S è la mia stringa? Come mai ho a S a ??

[giozh]

i linguaggi context free sono i linguaggi generati dalle grammatiche di tipo 1, e rispetto a quelle di tipo 0 non "accorciano" le stringhe che generano. si chiamano context free perche nella parte sinistra è presente un non terminale, che non dipende dal contesto in cui si trova (vedi le grammatiche di tipo 2)
S di solito è l'assioma, ovvero la stringa da dove devi partire per generare tutte le stringhe possibili del linguaggio. le lettere maiuscole sono in non terminali, mentre le minuscole sono i terminali. una stringa deve essere composta da soli non terminali. S-->aSa gignifica che tu all'inizio parti da S per generare la tua stringa, e ogni volta che nella stringa troverai la S la dovrai sostituire con aSa. applicando due volte la produzione ottieni aaSaa. quest'unica produzione però non ti genera nessuna stringa di nessun linguaggio, perchè non arriverai mai ad avere una stringa di non terminali. se avevi una cosa del genere invece(esempio banalissimo):
S-->aBc
B-->b
partivi dall'assioma S, e lo sostituivi con aBc. ora la B la puoi sostituire con b e ottieni abc.

[linuxloverstaff]

"starsuper": ad esempio S-->aSa, cosa siginifica?

Nello specifico la tua stringa di partenza diventa una stringa che è composta da a.S.a dove S sta ad indicare che puoi ancora lavorare sulla stringa, ovvero applicando ancora S nel punto indicato avrai:

aa.S.aa

S è una variabile non terminale. Se avevi per esempio:

S->aBa
B->a

Allora dopo aver applicato S avresti potuto applicare solo B e niente altro.

Saresti arrivato a:

aaa