1
$\begingroup$

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??

Improve this question
$\endgroup$
8
  • $\begingroup$ 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 cs.stackexchange.com/a/68106 (no two different productions have the same terminal prefix), the $S\to(S)S\mid\epsilon$ grammar is deterministic. $\endgroup$
    – Emil Jeřábek
    Commented Mar 14 at 8:33
  • 2
    $\begingroup$ In any case, this question would be more appropriate at cs.stackexchange.com . $\endgroup$
    – Emil Jeřábek
    Commented Mar 14 at 8:34
  • $\begingroup$ 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. $\endgroup$
    – Jerry Ding
    Commented Mar 14 at 8:39
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Mar 14 at 8:39
  • $\begingroup$ 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. $\endgroup$
    – Jerry Ding
    Commented Mar 14 at 8:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.