HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Do CFGs generate many languages?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
languagesgeneratecfgsmany

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#65970, answer score: 8

Revisions (0)

No revisions yet.