Is there inherently ambiguous language which can not be recognized by Deterministic LBA?
For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityIs there inherently ambiguous language which can not be recognized by Deterministic LBA?
For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
Every context-free language, whether inherently ambiguous or not, is recognized by some deterministic LBA. This is Exercise 9.8 (a) in Hopcroft and Ullman's Introduction to Automata Theory, Languages, and Computation. Even more is true; see Exercise 9.8 (b).