Talk:Deterministic context-free grammar

Reworking the page

I'm considering fleshing out this stub. I'm planning on adding a formal definition, more background, and a few more examples. Also, the history and current use of deterministic context-free grammars would be nice. Any comments or ideas? Stratsve (talk) 05:08, 25 February 2008 (UTC)

Yes, also these are exactly the well known LR grammars. —Preceding unsigned comment added by 186.124.33.244 (talk) 13:50, 1 October 2009 (UTC)

I wouldn't mind seeing an example of a grammar that is context-free but not deterministic-context-free. --Doradus (talk) 14:17, 10 November 2009 (UTC)

This article has serious correctness issues

See recent discussion at the CS stack exchange.

PhS (talk) 13:31, 25 May 2014 (UTC)

Confirmed. "Deterministic Context-Free Grammar" is not a well-defined term. What however is well-defined is "a Deterministic Context-Free Language". But there is already an article on that! This article might need to be deleted. --Svennik (talk) 18:03, 29 March 2026 (UTC)

I agree that the page can be deleted. Note however that algorithms on compressed words often describe the SLP model as "acyclic deterministic CFG", where they use deterministic to mean that there is exactly one rule for each non-terminal. In effect, a SLP is a grammar that defines a singleton language. PhS (talk) 06:10, 24 April 2026 (UTC)

The CS stack exchange, is not, a reliable source.

This conversation is not well-informed. A "Deterministic Context-Free Grammar" is, a grammar which generates a "Deterministic Context-Free Language". That is the relationship of a generative grammar to a language in formal language theory (a relationship which goes one way, by the way: that way). It's odd that everyone on this page feels so free discussing this subject, without grasping this most basic, first-day-of-lecture fact about the entire field.

You'll note that we have Context-free grammar, and we have Context-free language. This, too, is normal: the generator and the generated are not, surprise surprise, the same thing. So it's reasonable to have pages for both.

If you do a basic literature search for the string we're debating, you'll find that the objections here raised are missing their footwear: bootless, if you prefer.

If you have more than "I read it on Stack" or "Yep that's what I think" to add, let's hear it. ~2026-29512-73 (talk) 16:55, 3 August 2026 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Deterministic context-free grammar. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20120405124425/http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf to http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 20:26, 11 December 2016 (UTC)