2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – chi Apr 29 '17 at 13:25
  • $\begingroup$ 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? $\endgroup$ – user337258 Apr 29 '17 at 13:38
  • 1
    $\begingroup$ 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). $\endgroup$ – Raphael Apr 29 '17 at 14:07
  • $\begingroup$ 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? $\endgroup$ – babou Apr 30 '17 at 11:57
1
$\begingroup$

The definition you state is for noncontracting grammars, which define the context-sensitive languages (modulo the issue of the empty word). In contrast, context-free grammars define the context-free languages, which are a strict subset of the context-sensitive languages.

So whoever told you that a Type 1 grammar is context-free iff it is noncontracting, used highly idiosyncratic terminology. Or perhaps they just made a mistake.

The Wikipedia article mentions a paper of Chomsky in which noncontracting grammars are called "Type 1". In an earlier paper of Chomsky, he used "Type 1" to mean context-free grammars. This might be the source of the confusion.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.