L1 is a Non Deterministic CFL as we can make a automata using a stack. We can push the string (w) in a stack and when two elements are same consecutively and we have two cases -
- It might be the starting of reverse of w. Say abba then w=ab , and when we get second b it is the starting of reverse string .
- It might just be a part of w . Say bbaabb Here second b is just a part of w.
So this PDA is non deterministic .
L2 is a Deterministic CFL . We can push the string (w) in a stack and we know as soon as we encounter # that's the beginning of reverse of w. And hence can represent it using a push down automata .
L3 is a context sensitive language as it can't be represented using a Push Down Automata as there is significance about when w ends and start again .