Efficient Solutions for the Complement of wwR and the Complement of ww
Allaoua Refoufi
Journal of Digital Information Management, Vol. 12, No. 6, 2014.
DOI: 
Link: http://dline.info/fpaper/jdim/v12i6/2.pdf
Abstract:
In this paper we propose a new approach to
tackle the problem of finding efficient non deterministic solutions for the complement of the language L1 = { wwR / w âˆˆ {0, 1}*} (the even length non palindromes) and the complement of the type 0 language (recursively enumerable) L2 = {ww / w âˆˆ {0, 1}*}. The solutions provided are very elegant and make a subtle use of non determinism. We show that these languages are context
free languages by designing non deterministic pushdown automaton that accepts them.