4
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ And even then it only needs a single epsilon rule from the start symbol. $\endgroup$ – rici Nov 13 '16 at 2:07
  • 2
    $\begingroup$ 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 $\endgroup$ – Rick Decker Nov 13 '16 at 21:49
  • $\begingroup$ @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). $\endgroup$ – Renato Sanhueza Nov 14 '16 at 0:21
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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