Is there a one to one correspondence?

Question

Is there a one to one correspondence between context free languages and context free grammars ?

---

What is the meaning of one to one correspondence here ? I know it is like proving bijection, but how is it phrased here(meaningfully) in the above statement ?

Answer 1

Let me give the example. Consider the vector space $\mathbb{R}^n$. There is one to one correspondence between linear isomorphisms of this space and nonsingular $(n\times n)$-matrices. Indeed, every linear isomorphism $\Phi\colon\mathbb{R}^n\to\mathbb{R}^n$ has the form $\Phi(x)=Ax$, where $A$ is a nonsingular matrix. Conversely, for each nonsingular matrix the mapping $A$ defining $\Phi(x)=Ax$ we arrive at the linear isomorphism. Of course, it is easy to prove the uniqueness of a matrix and of the isomorphism.

The correspondence of such type is of course a bijection between the appropriate sets. Here between the set of all linear isomorphism and the set of all nonsingular matrices.

Another example: the car and its VIN number.

Answer 2

For this specific question, I would say the answer is no, in the sense that each context-free language can have, in principle, any number of distinct context-free grammars which generate it. For example, one can take any grammar $G$ with starting symbol $S$, and create N replicas $G_1$, ..., $G_N$, with starting symbols $S_1$, ..., $S_N$ [by subscripting each non-terminal N times], and combining them into a single grammar by adding a new starting symbol $S_0$ and production $S_0$ --> $S_1$ | ... | $S_N$. And that's not the only trick one can do. On a more serious note, for context-free languages which have deterministically-parsible grammars, there are usually ways to rewrite the grammars to form the basis of a top-down parser, and other ways to rewrite the grammar to form the basis of a bottom-up parser.