# How can CFGs have epsilon rules if CSG may not have them?

I am new to theory of computer science and I am currently reading about CTF grammars. In our lecture we defined that a Type 1 grammar is context-free if for $w_1 \to w_2$, $\vert w_1 \vert \leq \vert w_2 \vert$.

I looked on the internet for an example and found this context-free grammar for palindromes: $G = \{\{P\},\{0,1\},A,P\}$ with the production rules: $P \to \epsilon|0|1|0P0|1P1$, but aren't those production rules violating the definition for a CTF? First of all $\vert w_1 \vert \leq \vert w_2 \vert$ is violated by $P\to\epsilon$ and secondly in my notes there is mentioned that we can only use an epsilon transition if P isn't on the right site.

• In a context free grammar, $w_1$ can be only a single non terminal, and $w_2$ can be arbitrary, including empty. Check your definition again, maybe it's defining something else. – chi Apr 29 '17 at 13:25
• Oh yeah, I looked at the def. of context-sensitive. But a Typ2 grammar has to be type1, so the rule with less-equal holds as well, or am I wrong? – user337258 Apr 29 '17 at 13:38
• Does it say that every type 2 grammar is a type 1 grammar? The hierarchy is for languages, not necessarily grammars. Note also that many different, equivalent definitions are around for each level. For instance, there are normal forms for CFGs that don't use epsilon rules (except maybe for the empty word). – Raphael Apr 29 '17 at 14:07
• Does CTF mean context-free? I do not recall ever encountering this notation. According to Google, It seem to be used, though I did not see a definition. Maybe it is just my memory? Is it in Chomsky's original papers, or is there a reference? – babou Apr 30 '17 at 11:57

Finally, to answer the question in your title: noncontracting grammars only define the context-sensitive languages without $\epsilon$. Conversely, the context-free languages without $\epsilon$ are defined by context-free grammars without $\epsilon$ productions (this follows from Chomsky normal form, for example). In this sense a noncontracting grammar is a generalization of a context-free grammar, in both cases for languages without $\epsilon$. If you want to include also languages with $\epsilon$, you need to consider essentially noncontracting grammars instead; these are also allowed to contain the product $S\to\epsilon$, assuming $S$ doesn't appear in the right-hand side of a production.