Quando si deve dare una CFG, oltre alle regole, fare anche un esempio di parsing.
Se è richiesto un caso particolare (es. se una CFG è ambigua, o l'applicazione a una stringa data) va messo l'albero di derivazione.
L'albero deve includere le ε, se richieste, e il simbolo iniziale.
Esempio: {aibjck | i = j or j = k, where i, j, k ≥ 0}
S = D | E
D = Dc | Fc
E = aE | aG
F = aFb | ε
G = bGc | ε
Dire se la grammatica è ambigua
S S
| |
D E
+---+---+ +---+---+
D c a E
+--+--+ +---+---+
a D b b E c
| |
ε ε
Quando chiede di dimostrare qualcosa usando dei linguaggi, non dare per scontato che siano context-free.
Usare una grammatica o un PDA per dimostrare che lo sono.
USARE GRAMMATICHE E NON PDA PER DIMOSTRARE COSE.
Quando si uniscono o concatenano grammatiche diverse, fare attenzione al nome dei terminali: se due terminali in grammatiche diverse hanno lo stesso nome, fondendo le grammatiche si uniscono anche i nomi dei terminali!
Se necessario, aggiungere pedici con un numero progressivo.
Esempio:
G: S1 → A, A → aB, B → bB|ε
H: S2 → AB, A → c, B → d
l'unione può portare a S → S1 → A → c, che è palesemente un comportamento indesiderato.