<p>I know that it's possible to build an LL(1) parser for the Dyck language, i.e. a balanced string of parentheses, so the Dyck language is a deterministic context-free language.</p>
<p>But what's an example of a deterministic context-free grammar that matches this language? I'm finding it surprisingly hard to construct one.</p>
<p>According to <a href="https://cs.stackexchange.com/questions/14583/how-is-non-ambuiguity-different-from-determinism">here</a> and <a href="https://cs.stackexchange.com/questions/85088/understanding-definitions-of-deterministic-context-free-grammar-and-deterministi">here</a>, a DCFG is a CFG where for each non-terminal, the production rules do not share the same prefix of non-terminals.</p>
<p>The common way of matching the Dyck language with a CFG is this (<code>e</code> is <span class="math-container">$\epsilon$</span>):</p>
<pre><code>S -&gt; (S)S | e
</code></pre>
<p>This is not a DCFG because the two production rules share the same prefix of non-terminals, which is the empty string. I'm having a hard time modifying this so that there is no common prefix. The best I was able to achieve is this:</p>
<pre><code>A -&gt; (BA |  $
B -&gt;  )  | (BB
</code></pre>
<p>This generates balanced parenthesis followed by the symbol <code>$</code>. If you insist that there be no ending <code>$</code>, is the language suddenly not deterministic anymore??</p>

CC BY-SA 4.0
2024-03-14T08:33:19.733Z
I am not familiar with this definition of a DCF *grammar*. Usually, deterministic context-free *languages* are defined as those that can be recognized by a DPDA, not by a property of grammars. But according to the definition given in your link https://cs.stackexchange.com/a/68106 (no two different productions have the same *terminal* prefix), the $S\to(S)S\mid\epsilon$ grammar *is* deterministic.
Emil Jeřábek
CC BY-SA 4.0
2024-03-14T08:34:22.193Z
In any case, this question would be more appropriate at https://cs.stackexchange.com .
Emil Jeřábek
CC BY-SA 4.0
2024-03-14T08:39:05.750Z
I am happy to have the question moved, I currently haven't used StackExchange long enough to perform the move myself.

If the empty prefix doesn't count, then the language of palindromes is also deterministic ($S \rightarrow 0S0 | 1S1 | \epsilon$), but it is well-established that this is not true. I think it's because the empty prefix does count as being repeated in the productions.
Jerry Ding
CC BY-SA 4.0
2024-03-14T08:39:33.757Z
Though your second link makes a good case that the given definition of deterministic grammars is simply wrong, as such grammars may generate languages that are not DCFL. Do you have any *real* source for this (or any) definition of a DCFG, apart from an anonymous guy saying it on the internet? Otherwise I’d suggest you just forget about it, and use the standard definition with DPDA.
Emil Jeřábek
CC BY-SA 4.0
2024-03-14T08:44:59.137Z
Good point, I tried looking just now and did not find a more official source for the definition of a DCFG. Perhaps the term is not well-defined, or that its definition is very indirect, i.e. any CFG whose language is a DCFL.
Jerry Ding
CC BY-SA 4.0
2024-03-14T11:20:40.540Z
I see that you perhaps interpret the condition so that different production rules have to have terminal prefixes that are not prefixes of each other (which indeed guarantees that the language is deterministic). This almost entirely prevents $\epsilon$ productions, hence such grammars cannot generate any DCFL containing $\epsilon$ except for $\{\epsilon\}$. Moreover, I think I agree with your impression that such a grammar cannot generate the Dyck language (even minus $\epsilon$).
Emil Jeřábek
CC BY-SA 4.0
2024-03-14T11:52:59.183Z
That makes sense, I guess it's an interesting question whether this weird definition of a DCFG is able to generate any DCFL provided you first append `$` to all strings in the language... any case you answered all I needed to know from the question, thanks!
Jerry Ding
CC BY-SA 4.0
2024-03-14T12:16:34.200Z
My conjecture is that that question can be answered (most likely negatively) by looking up the definitions of LL(k), LR(k), SLR(k), etc. grammars, and figuring out how the proposed definition of “DCFG” fits in.
Emil Jeřábek
<fl.formal-languages><context-free><parsing>
Not possible to write deterministic CFG for balanced parenthesis?
Jerry Ding
# Not possible to write deterministic CFG for balanced parenthesis?

(Asked by: username_0 on 2024-03-14)

I know that it's possible to build an LL(1) parser for the Dyck language, i.e. a balanced string of parentheses, so the Dyck language is a deterministic context-free language.
But what's an example of a deterministic context-free grammar that matches this language? I'm finding it surprisingly hard to construct one.
According to here and here, a DCFG is a CFG where for each non-terminal, the production rules do not share the same prefix of non-terminals.
The common way of matching the Dyck language with a CFG is this (e is $\epsilon$):
S -> (S)S | e

This is not a DCFG because the two production rules share the same prefix of non-terminals, which is the empty string. I'm having a hard time modifying this so that there is no common prefix. The best I was able to achieve is this:
A -> (BA |  $
B ->  )  | (BB

This generates balanced parenthesis followed by the symbol $. If you insist that there be no ending $, is the language suddenly not deterministic anymore??

**Tags:** fl.formal-languages, context-free, parsing

> **Comments:**
> **username_1**: I am not familiar with this definition of a DCF *grammar*. Usually, deterministic context-free *languages* are defined as those that can be recognized by a DPDA, not by a property of grammars. But according to the definition given in your link https://cs.stackexchange.com/a/68106 (no two different productions have the same *terminal* prefix), the $S\to(S)S\mid\epsilon$ grammar *is* deterministic.  
> **username_1**: In any case, this question would be more appropriate at https://cs.stackexchange.com .  
> **username_0**: I am happy to have the question moved, I currently haven't used StackExchange long enough to perform the move myself.  If the empty prefix doesn't count, then the language of palindromes is also deterministic ($S \rightarrow 0S0 | 1S1 | \epsilon$), but it is well-established that this is not true. I think it's because the empty prefix does count as being repeated in the productions.  
> **username_1**: Though your second link makes a good case that the given definition of deterministic grammars is simply wrong, as such grammars may generate languages that are not DCFL. Do you have any *real* source for this (or any) definition of a DCFG, apart from an anonymous guy saying it on the internet? Otherwise I’d suggest you just forget about it, and use the standard definition with DPDA.  
> **username_0**: Good point, I tried looking just now and did not find a more official source for the definition of a DCFG. Perhaps the term is not well-defined, or that its definition is very indirect, i.e. any CFG whose language is a DCFL.  
> **username_1**: I see that you perhaps interpret the condition so that different production rules have to have terminal prefixes that are not prefixes of each other (which indeed guarantees that the language is deterministic). This almost entirely prevents $\epsilon$ productions, hence such grammars cannot generate any DCFL containing $\epsilon$ except for $\{\epsilon\}$. Moreover, I think I agree with your impression that such a grammar cannot generate the Dyck language (even minus $\epsilon$).  
> **username_0**: That makes sense, I guess it's an interesting question whether this weird definition of a DCFG is able to generate any DCFL provided you first append `$` to all strings in the language... any case you answered all I needed to know from the question, thanks!  
> **username_1**: My conjecture is that that question can be answered (most likely negatively) by looking up the definitions of LL(k), LR(k), SLR(k), etc. grammars, and figuring out how the proposed definition of “DCFG” fits in.  

---

## 0 answers

