Find a non-deterministic CFL whose reverse is deterministic

Question

I have a homework assignment, and i am finished other then one question (see title)

For the life of my, i cannot figure this out... so i started to think it was a trick question.

the current answer that i will submit is:

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

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

On a side note, the only other example i was trying to make work is:

L3= {{a,b}a}

This seems possible because forward there is non-determinism, since the input could be either a, or b as long as its followed by an a.

and in reverse there is determinism since it will accept only an 'a'. But, it introduces new non-determinism since the second input could be either a or b.

any help / guidance would be great.

Answer 1

I know the deadline has passed, but somebody might find this useful in the future.

(a+b+c)*WcW^R, where W is in (a+b)+; this is non-deterministic because you don't know where the "WcW" bit starts.

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 accepting state to loop to itself on any of a, b and c.

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