Talk:Deterministic context-free language

Linguistics: Philosophy of language Low‑importance

	Linguistics portal This article is within the scope of WikiProject Linguistics, a collaborative effort to improve the coverage of linguistics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.LinguisticsWikipedia:WikiProject LinguisticsTemplate:WikiProject LinguisticsLinguistics articles
Low	This article has been rated as Low-importance on the project's importance scale.
	This article is supported by Philosophy of language task force.

Philosophy: Logic Mid‑importance

This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Associated task forces:
/
	Logic

Computer science High‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

[edit]

I believe this is equivalent to the set of non-ambiguous context-free grammars? If it is then this would be useful to include on this page.

Not that simple. All DCFLs have unambiguous CFGs, but is a proper subset. Per Hopcroft, Motwani & ullman, Intro automata theory, languages and computation, 2nd edition. Added to article. (See example of unambig CFG that is not DCFG now in article). RJFJR 00:08, 12 April 2007 (UTC)[reply]

Removed the word "obviously" because I honestly can't see why that CFG is not a DCFG. Rhebus 15:23, 6 June 2007 (UTC)[reply]

This is not true. As cited here (this is also my textbook, published in 2010), and as stated by my professor, it is currently unknown if the deterministic context-free languages are a proper subset of the context-free languages or equivalent to them. The statement from the citation is "There are still open questions concerning context-sensitive languages, such as whether or not every CSL can be accepted by a deterministic LBA." An LBA is a linear-bounded automaton, and the set of languages accepted by deterministic LBA's is precisely the deterministic context-free languages. Therefore, the claim that deterministic context-free languages are a proper subset of the context-free languages is false - we simply don't know if they are a proper subset or equivalent yet. — Preceding unsigned comment added by 165.82.203.181 (talk) 01:13, 30 April 2015 (UTC)[reply]

Actually, they are a proper subset: see p. 133 of Michael Sipser's Introduction to the Theory of Computation. --128.2.100.145 (talk) 03:04, 6 May 2015 (UTC)[reply]

Poor Example[edit]

The example (palindrome language) as stated is lacking the clear problem description (what is being claimed) and does not show contradiction (necessary to negate the... khm... non-existing problem description). What it claims now is "An arbitrary string of this language cannot be parsed without reading all its letters first", which is not a contradiction, neither is it impossible to do, quite the contrary, in order to parse a language you would need to read "all its letters first". It doesn't logically follow from the fact that a PDA has to read all the letter that it has to alternate states. Maybe the language that is described by the given grammar is indeed non-deterministic, but no real argument is presented to support this claim. My guess is that the argument didn't preserve well after being taken from the source. 109.65.104.130 (talk) 19:38, 25 September 2013 (UTC)[reply]

Recognition[edit]

Is there an algorithm to recognize that a grammar has a DCFL? RJFJR (talk) 13:59, 20 May 2014 (UTC)[reply]

No, it is undecidable whether a given context-free grammar describes a DCFL. Also, the trade-off in the worst-case size of automata when moving from nondeterministic pushdown automata to deterministic pushdown automata is a function that grows faster than any recursive function (a "non-recursive trade-off"). For comparison, it is well known that the trade-off in the worst-case size of automata when moving from nondeterministic finite automata to deterministic finite automata is at most exponential, by means of the subset construction. The mentioned results are covered in the following papers:

Juris Hartmanis: On the Succinctness of Different Representations of Languages. SIAM Journal on Computing 9(1): 114-120 (1980).
Martin Kutrib: The phenomenon of non-recursive trade-offs. International Journal of Foundations of Computer Science 16(5): 957-973 (2005).

Hermel (talk) 18:41, 17 May 2015 (UTC)[reply]

Clarification needed[edit]

Can someone clarify this ungrammatical clause in the second sentence of the article: "but any (non-empty) DCFLs also admit ambiguous grammars"? Two possibilities are (1) "but some (non-empty) DCFLs also admit ..." and (2) "but any (non-empty) DCFL also admits ...". Mdmi (talk) 12:26, 23 June 2016 (UTC)[reply]

Definition/explanation[edit]

This page would greatly benefit from a formal definition of its subject, and/or a more detailed technical explanation. Of course they are exactly the languages that can be parsed using a deterministic pushdown automaton, but what does that mean in practice, in terms of how such a grammar is specified? Nathaniel Virgo (talk) 09:58, 18 February 2017 (UTC)[reply]