-1
$\begingroup$

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$ ?

$\endgroup$
5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.