[Grammatica Libera Dal Contesto] Dubbio generazione grammatica

[Mozaic83]

Ciao a tutti, sto studiando gli automi e le grammatiche e mi servirebbe un aiuto.

Ho questo esercizio da risolvere e vorrei un vostro parere sulla risoluzione che ho fatto:

Λ = {a, b, c, d}
L= {a^n b^m c^(2(n+m)+1) d | n ≥ 0 , m > 0}

Questo è quello che ho capito:
La d finale è fissa e deve rimanere unica
la b la c ci sono sempre e la stringa base generabile è bcccd
Per ogni n che aumenta di 1 => aumento di una a e di due c
Per ogni m che aumenta di 1 => aumento di una b e di due c

Io l'ho risolto così, ma ho un po' di dubbi, soprattutto sulla seconda regola:

S0 => S1 d

S1 => ε (insieme vuoto) => questa regola l'ho pensata perchè c'è un caso con n=0 (dove a non esiste e le c non aumentano)

S1 => a S1 cc

S2 => bccc

S2 => b S2 cc

S1 => S2

[wingman87]

Va bene però bisogna togliere

S1 => ε (insieme vuoto) => questa regola l'ho pensata perchè c'è un caso con n=0

perché nel caso n=0 si passa direttamente per

S1 => S2

Altrimenti sarebbe possibile generare (ad esempio) la stringa "d" o "accd"

[Mozaic83]

Originariamente inviato da wingman87

Va bene però bisogna togliere

S1 => ε (insieme vuoto) => questa regola l'ho pensata perchè c'è un caso con n=0

perché nel caso n=0 si passa direttamente per

S1 => S2

Altrimenti sarebbe possibile generare (ad esempio) la stringa "d" o "accd"

Grazie per la risposta, avevo anch'io dei dubbi sull'utilità di quella produzione

[DanieleC88]

A prima vista pare corretta, ma secondo me te la puoi cavare con molto meno:

S → Mcd
M → aMcc | B
B → bBcc | bcc

Se non ho capito male, questa grammatica dovrebbe generare tutte le stringhe nel linguaggio.

ciao

EDIT: che in realtà a ben vedere hai solo aggiunto più produzioni separatamente invece che con una disgiunzione, ma siamo lì... Unica cosa, la c aggiuntiva (del 2(n+m)+1) ci sarà sempre, per cui puoi inserirla direttamente nella produzione iniziale.