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$ ?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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).
