Generare una grammatica context-free

[ludovica.sarandrea]

Buongiorno, ho un problema di informatica teorica. Ho un esercizio che si sviluppa in due punti:
-generare una grammatica context-free dato il linguaggio $L={a^n w a^m | w=aba$ oppure w=abba e $m=2n$ con $m,n>0}$
-generare una grammatica context-free dato il linguaggio delle parole che hanno lunghezza dispari e il primo elemento e' diverso da quello centrale e da quello finale (es. [size=150]a[/size]ba[size=150]b[/size]ba[size=150]b[/size]}
entrambi i linguaggi sono sull'alfabeto ${a,b}$

Io ho svolto il primo punto cosi:
$S->aSaa|W$
$W->aba$|abba
e' corretto??

per il secondo punto non ho proprio idee...

[apatriarca]

Il primo punto mi sembra abbastanza corretto, eccetto per la condizione \(m, n > 0\). Se infatti partiamo da S e scegliamo subito la seconda regola abbiamo una parola che non è nel linguaggio: \(aba\) oppure \(abba\).

Per il secondo credo farei qualcosa come il seguente (non sono un esperto per cui potrei aver fatto errori - è più una indicazione su come procedere che una soluzione):
\[ \begin{align*}
S &\to aAb \mid bBa \\
A &\to aAa \mid aAb \mid bAa \mid bAb \mid b \\
B &\to aBa \mid aBb \mid bBa \mid bBb \mid a \\
\end{align*} \]

[ludovica.sarandrea]

"apatriarca":Il primo punto mi sembra abbastanza corretto, eccetto per la condizione \(m, n > 0\). Se infatti partiamo da S e scegliamo subito la seconda regola abbiamo una parola che non è nel linguaggio: \(aba\) oppure \(abba\).

Per il secondo credo farei qualcosa come il seguente (non sono un esperto per cui potrei aver fatto errori - è più una indicazione su come procedere che una soluzione):
\[ \begin{align*}
S &\to aAb \mid bBa \\
A &\to aAa \mid aAb \mid bAa \mid bAb \mid b \\
B &\to aBa \mid aBb \mid bBa \mid bBb \mid a \\
\end{align*} \]

grazie mille!
per il primo come posso risolvere?