Deterministic Context free languages are always unambiguous. Now DCFL are a subset of linear languages. Are there any linear languages which are inherently ambiguous?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The linear language $\{ a^ib^jc^k \mid i=j \text{ or } j=k\}$ is inherently ambiguous.
answered Oct 21, 2017 at 12:26
-
$\begingroup$ Question has a sentence saying "DCFL are a subset of linear languages." Is it correct? Wikipedia says: "linear languages that are regular languages are deterministic". And we know that there are DCFLs which are not regular. Hence, there must exists DCFLs which are not linear. Correct? $\endgroup$– RajSCommented Nov 9, 2019 at 20:23
-
1$\begingroup$ Good observation. There are indeed nonlinear DCFL. An example is the set of strings with matching parentheses. $\endgroup$ Commented Nov 10, 2019 at 10:26