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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ How is the given language given? $\endgroup$– adrianNJul 21, 2016 at 10:44
-
$\begingroup$ @adrianN Assume it is given as a regular expression $\endgroup$– ethaneJul 21, 2016 at 11:01
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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:
- For every $x \in L(G)$ we have $x \in S$.
- 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.
answered Jul 21, 2016 at 11:00
-
$\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$– ethaneJul 21, 2016 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$ Jul 21, 2016 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, 2016 at 14:54
$\begingroup$
$\endgroup$
5
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.
- Prove that $G$ is regular
- 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$– ethaneJul 21, 2016 at 13:14
-
-
$\begingroup$ @Ethan That's an entirely different question. $\endgroup$– Raphael ♦Jul 21, 2016 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$ Jul 21, 2016 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$– adrianNJul 22, 2016 at 8:27