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?
Asked By : socrates
Answered By : Raphael
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/65970
0 comments:
Post a Comment
Let us know your responses and feedback