# Is my grammar correct and context free?

I have this language

$$L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$$.

I have to determine a free context grammar that generates L. Looks easy BUT i have a question about the grammar I found. First things first, this is my grammar:

$$S \Rightarrow BC$$

$$B \Rightarrow aBbbb\ \backslash \ abbb$$

$$C \Rightarrow Ccc \ \backslash \ cc$$

Looks easy and clean to me. I already tested it with strings of different lengths and seems working just fine. Also it does indeed create only strings contained in L and no other strings.

My question is:

This is the first time I generate a grammar without any production containing $$S$$ itself (An example would be adding $$S \Rightarrow B$$ and I would solve my problem, because B generates only $$a$$'s and $$b$$'s and the number of this chars is dipendent between one another but indipendent with the number of $$c$$'s inside the string).

Recursively speaking, this works just fine but using $$S$$ would induce me to create a noncontracting language (because I'd be forced to invert some Non Terminals in order to produce both $$a$$'s and $$b$$'s correctly if something is wrong in my grammar). Is this way of creating grammars correct? Can I describe what I wrote as an actual "grammar"? Is it context free?

Also, can I actually derivate $$a$$ through $$B$$ without a nonterminal $$A$$ and without generating it with the $$S$$ production?

• Whether it's context-free is an easy, syntactical check. Read the definition carefully. Regarding correctness, have you tried a formal proof? – Raphael Mar 2 at 18:53
• I merely asked if it is generally allowed to use a starting terminal without a production containing S itself. I already read extensively that thread and it helped me a great deal. Mine was a much simplier question and it's all about technique – niciola Mar 2 at 19:21
• In that case, please edit to focus on that question. – Raphael Mar 2 at 22:08

Your context-free grammar is just fine. It is not actually necessary for the grammar to have a production with $$S$$ in its right-hand side. In fact, a context-free grammar need not have any recursive productions or mutually-recursive productions, though the generated language in that case may be quite limited. It is also not necessary to use any particular names for your nonterminals (e.g there is no need for $$A$$ to appear anywhere).
• 1) "may be quite limited" = "would be finite" 2) Naming conventions are necessary if you leave out the canonical $G = (S, N, T, \delta)$ -- without it, you don't know what's what! – Raphael Mar 2 at 22:11
Check your definitions. Mine says there is an alphabet of nonterminals $$N$$, an alphabet of terminals $$\Sigma$$ (where $$N \cap \Sigma = \varnothing$$, essentially "you can tell what is what"), a finite set of productions of the form $$A \to \alpha$$, where the left hand side $$A \in N$$ (a single non-terminal) and the right hand side $$\alpha \in (N \cup \Sigma)^+$$ (terminals and non-terminals in any order, at least one; you can allow empty right hand sides as an extension), one of the nonterminals is designated as starting symbol.