Find a non-deterministic CFL whose reverse side is deterministic

Question

I have homework and I finished another, then one question (see name)

In my life, I can’t understand this ... so I began to think that it was a trick.

The current answer that I will give you is:

L1 = {a^nb^n: n>=1} is deterministic. And the reverse, L2 = {b^na^n: n>=1} is also deterministic. 

However, since all deterministic languages ​​are a subset of the non-deterministic languages, L2 can be considered non-deterministic.

On the side of the note, the only other example I tried to do is this:

 L3= {{a,b}a} 

This seems possible because there is no non-determinism ahead, since the input can be either a or b, as long as it follows a.

and vice versa, determinism exists, since it accepts only "a". But it introduces a new non-determinism, since the second input can be either a or b.

Any help / guidance would be wonderful.

Answer 1

I know the deadline has passed, but someone may find this useful in the future.

(a + b + c) * WcW ^ R, where W is in (a + b) +; it is not deterministic because you do not know where the "WcW" bit begins.

W ^ RcW (a + b + c) *, where W is in (a + b) +; this is deterministic because you can write a deterministic PDA to accept simple palindromes of the form "W ^ RcW" and modify the receiving state for the loop to itself on any of a, b and c.

The trick here is that PDAs must read input from left to right.