Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree?

What if the tree is infinite? What would then be a better way to prove that a given CFG generates a given language?

  • 1
    $\begingroup$ How is the given language given? $\endgroup$ – adrianN Jul 21 '16 at 10:44
  • $\begingroup$ @adrianN Assume it is given as a regular expression $\endgroup$ – ethane Jul 21 '16 at 11:01

Suppose that we have a context-free grammar $G$ and a set of words $S$, and we would like to prove that the language $L(G)$ generated by $G$ is precisely the set $S$. The most direct way of doing this is to prove $L(G) \subseteq S$ and $S \subseteq L(G)$, which amounts to showing:

  1. For every $x \in L(G)$ we have $x \in S$.
  2. For every $y \in S$ we have $y \in L(G)$.

How this is done depends on how the set $S$ is given, so there is no further, more specific advice that I can offer, except that drawing trees is not really going to result in a proof.

  • $\begingroup$ Would a proof for this then be similar to an informal proof of propositional calculus? Stating the language and then stating the productions that can be used to generate the words in L? $\endgroup$ – ethane Jul 21 '16 at 11:11
  • $\begingroup$ Just stating what $G$ and $S$ are is not a proof, that's the preparation. The proof will be like any kind of mathematical proof. For instance, the first point above would start as: "Consider an arbitrary $x \in L(G)$. There exists a sequence $p_1, \ldots, p_n$ in $G$ of production rules which generate $x$. Now observe that bla bla bla ... more bla bla ... therefore $x \in S$." $\endgroup$ – Andrej Bauer Jul 21 '16 at 14:26
  • 1
    $\begingroup$ We have a reference question that attempts to give some general advice on how to construct such proofs. $\endgroup$ – Raphael Jul 21 '16 at 14:54

If your language $L$ is, as you state in the comment, given as a regular expression, you can prove that the grammar $G$ generates it in two steps.

  1. Prove that $G$ is regular
  2. Show that the two automatons (from $G$ and from the expression for $L$) recognizing the language are the same.
  • $\begingroup$ Assuming a language L is indeed regular and therefore given in regular expression form. And to prove that some CFG accepts L, could the use of pumping lemma be used to inductively prove that the CFG generates all words in L and all words in L are generated by the CFG? $\endgroup$ – ethane Jul 21 '16 at 13:14
  • $\begingroup$ What if $G$ is not regular? $\endgroup$ – Raphael Jul 21 '16 at 14:55
  • $\begingroup$ @Ethan That's an entirely different question. $\endgroup$ – Raphael Jul 21 '16 at 14:55
  • $\begingroup$ Assuming that grammar $G$ is a CFG as in the question your approach looks like an algorithm, but it can't be one. It is undecidable whether a CFG generates a regular language (item 1), and I seem to remember that even if you happen to know $L(G)$ is regular then one cannot find a finite automaton for it (item 2). $\endgroup$ – Hendrik Jan Jul 21 '16 at 15:20
  • $\begingroup$ @HendrikJan I think most interesting things you want to prove don't have an algorithm. It's also undecidable whether an algorithms runs in O(n) or O($n^2$), but we still do that quite often. $\endgroup$ – adrianN Jul 22 '16 at 8:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.