[LF] produzioni contestuali
Ciao a tutti!!
Mi scuso in anticipo per la banalità delle domande, tuttavia sono un po' confuso per quanto riguarda le grammatiche CS (context-sensitive).
Allora per definizione una grammatica è CS se ogni sua produzione è in una delle seguenti forme:
$1) yAz->ywz$
con y e z che possono essere composte da terminali, non terminali oppure possono essere stringhe vuote
e w che può essere composta da terminali o non terminali.
$2) S->lambda$
purché $S$ non compaia a destra di alcuna produzione.
a questo punto mi chiedo produzioni del tipo
$aB->bB$ sono contestuali?
Mi scuso in anticipo per la banalità delle domande, tuttavia sono un po' confuso per quanto riguarda le grammatiche CS (context-sensitive).
Allora per definizione una grammatica è CS se ogni sua produzione è in una delle seguenti forme:
$1) yAz->ywz$
con y e z che possono essere composte da terminali, non terminali oppure possono essere stringhe vuote
e w che può essere composta da terminali o non terminali.
$2) S->lambda$
purché $S$ non compaia a destra di alcuna produzione.
a questo punto mi chiedo produzioni del tipo
$aB->bB$ sono contestuali?
Risposte
Beh, applicando la definizione, tu cosa ne dici?
Prima di tutto grazie per avermi risposto.
Io dico di no perché così viene riscritto il terminale non il non-terminale, in pratica in $yAz->ywz$ la $A$ deve appartenere all'alfabeto dei simboli non terminali.
Dico bene?
quindi stessa cosa per produzioni del tipo
$aBB->bBB$
o mi sfugge qualcosa?
Io dico di no perché così viene riscritto il terminale non il non-terminale, in pratica in $yAz->ywz$ la $A$ deve appartenere all'alfabeto dei simboli non terminali.
Dico bene?
quindi stessa cosa per produzioni del tipo
$aBB->bBB$
o mi sfugge qualcosa?
E' giusto; anche (forse più semplicemente?) in base alla definizione $aB -> bB$ non è nella forma corretta ($\alpha\N\beta -> \alpha\gamma\beta$):
- $\gamma='B', \beta='', \alpha=\?$
- $\gamma='b', \beta='B', \alpha=\?$
eccetera, dove non riesci a "costruire" una produzione CS. Idem per il tuo secondo esempio.
- $\gamma='B', \beta='', \alpha=\?$
- $\gamma='b', \beta='B', \alpha=\?$
eccetera, dove non riesci a "costruire" una produzione CS. Idem per il tuo secondo esempio.
Non ho capito bene quelle due righe che hai scritto, piùà che altro non riesco a capire i simboli non li ho mai incontrati prima, se ti va puoi spiegarmi...
mentre sono contestuali produzioni del tipo:
$aA->ab$ in questo caso il contesto sinistro è $a$ e il contesto destro è $lambda$ (stringa vuota)
$aBb->acb$ in questo caso il contesto sinistro è $a$ e il contesto destro è $b$
$Bb->bb$ in questo caso il contesto sinistro è $lambda$ e il contesto destro è $b$
non è contestuale:
$aA->Aa$
$aABa->bABb$
e via dicendo, ho detto bene?
mentre sono contestuali produzioni del tipo:
$aA->ab$ in questo caso il contesto sinistro è $a$ e il contesto destro è $lambda$ (stringa vuota)
$aBb->acb$ in questo caso il contesto sinistro è $a$ e il contesto destro è $b$
$Bb->bb$ in questo caso il contesto sinistro è $lambda$ e il contesto destro è $b$
non è contestuale:
$aA->Aa$
$aABa->bABb$
e via dicendo, ho detto bene?
"_overflow_":
...più che altro non riesco a capire i simboli non li ho mai incontrati prima, se ti va puoi spiegarmi...
Ho scritto le tue stesse cose, con notazione differente ($N$ è un non terminale, $\alpha, \beta, \gamma$ sono stringhe di terminali e non terminali).
Il resto che hai scritto è corretto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo