Efficient Solutions for the Complement of wwR and the Complement of ww.
Allaoua Refoufi · Journal of Digital Information Management · 2014
In this paper we propose a new approach to tackle the problem of finding efficient non deterministic solutions for the complement of the language L 1 = { ww R / w ∈ {0, 1}*} (the even length non palindromes) and the complement of the type 0 language (recursively enumerable) L 2 = {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.