# Do CFGs generate many languages?

Suppose we define a CFG such that it is possible to produce strings of the form $a^nb^n$ (in this case, I would think, we would need epsilon-productions). Then one such $L(CFG)$ is $a^nb^n$.

However, let's say it is also possible to produce strings not of the form $a^nb^n$ from this grammar.

Can we still call $a^nb^n$ a language generated by the grammar, even if it is not the only/unique language accepted by the grammar?

In other words, is the language accepted by a CFG the set of all strings that can be derived from the grammar? Or can it also be a proper subset of these strings, fulfilling some desired criterion?

## 3 Answers

Every grammar, by definition, generates a single, unique language.

The definition of "generating $L$" includes that $\overline{L}$ has to be not generated. That's obviously not the case for any proper subset of the "largest" generated language.

The definition has not been chosen without reason: using your approach, every formal language would be regular (as subset of $\Sigma^*$). That would not be a useful model at all.

If

$$L(CFG) = \mathscr{L}$$

and

$$\mathscr{L} \supset \{a^nb^n: n\geq 0\}$$

then $CFG$ accepts $\mathscr{L}$ and not $\{a^nb^n: n\geq 0\}$. Maybe one way to avoid this confusion is to use the word denote instead of accept. The grammar $CFG$ denotes the language $\mathscr{L}$. Anyways this should be clear by reading the definitions.

And $CFG$ is going to need $\epsilon$-production rules only if $n$ can be $0$. You should be more specific in the future.

• And even then it only needs a single epsilon rule from the start symbol. – rici Nov 13 '16 at 2:07
• A standard way of expression this is that a grammar $G$ generates strings and the language associated with a grammar, denoted by $L(G)$, is the set of all strings that can be generated by the grammar – Rick Decker Nov 13 '16 at 21:49
• @RickDecker Indeed it is a good way of expression the meaning of $L(G)$ and it serves as a remembrance for students that a language is simply a set of words(strings). – Renato Sanhueza Nov 14 '16 at 0:21

When in doubt, one should always consult the definition. The language generated by a context-free grammar $G = (V,\Sigma,R,S)$ is defined to be

$$L(G) = \{ w \in \Sigma^* \mid S \Rightarrow^* w \}$$

That is, $L(G)$ is the set of strings of terminal symbols that satisfy the condition, that they can be derived from the start symbol $S$ using the rules in $R$. By definition (and by the usual way of using set abstraction in mathematics), this set is unique.