snippetMinor
Do CFGs generate many languages?
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?
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.
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.