Jump to content

Talk:Deterministic context-free language

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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:
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]