<p><em>Every</em> 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 <em>Introduction to Automata Theory, Languages, and Computation</em>.  Even more is true; see Exercise 9.8 (b).</p>

CC BY-SA 3.0
2017-10-10T11:49:20.613Z
2017-10-10T11:49:20.613Z
Jeffrey Shallit
<p>Is there inherently ambiguous language which can not be recognized by Deterministic LBA?</p>

<p>For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?</p>

<complexity-classes><fl.formal-languages><computability><automata-theory>
Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?
XL _At_Here_There
# Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

(Asked by: username_0 on 2017-10-10)

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

**Tags:** complexity-classes, fl.formal-languages, computability, automata-theory

---

## 1 answers

### Answer by username_1 on 2017-10-10. Score: 5 | Accepted answer

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


---

