Grammatiche context free

[angel_j88]

Ciao a tutti, qualcuno sa se il linguaggio formato da tutte le stringhe non palindrome è context-free??? Io non riesco a trovare la grammatica che lo genera, però si sa che il linguaggio delle palindrome è context free ma anche che il complemento di un context free non è detto che sia ancora context free, sapete qualcosa ciao.

[euphoric]

$ V -> aVa | bVb | A $
$ A -> aBb | bBa $
$ B -> aBa | bBb | a | b | \epsilon $

does it work?

[m3ne1]

So che sono un po' in ritardo, ma per coloro che ne hanno bisogno (come ne ho avuto io poco fa), correggo la proposta semi-funzionante di euphoric:

V→aVa|bVb|A 
A→aBb∣bBa 
B→aBa|bBb|a|b|ϵ | A 

ho aggiunto alla fine la produzione A così funziona per un numero indefinito di parti non palindrome.