1
$\begingroup$

I am reading Chomsky's article Three models for the description of language, one of the earliest papers where context-free and context-sensitive grammars are mentioned. Essentially what he calls Phrase-structure-grammars in his article is nowadays called context-sensitive grammars. On page 118 he then introduces proper grammars:

[...] The grammar can also be simplified very greatly if we order the rules and require that they be applied in sequence (beginning again with the first rule after applying the final rule of the sequence), and if we distinguish between obligatory rules which must be applied when we reach them in the sequence and optional rules wich may or may not be applied. [...]

It seems reasonable to require for significance some guarantee that the grammar will actually generate a large number of sentences in a limited amount of time; more specifically, that it be impossible to run through the sequence of rules vacuously (applying no rule) unless the last line of the derivation under construction is a terminal string. We can meet this requirement by posing certain conditions on the occurrence of obligatory rules in the sequence of rules. We define a proper grammar as a system $[\Sigma, Q]$, where $\Sigma$ is a set of initial strings and $Q$ a sequence of rules $X_i \to Y_i$ [...] with the additional conditional that for each $i$ there must be at least one $j$ such that $X_i = X_j$ and $X_j \to Y_j$ is an obligatory rule. [...] Let $D(G)$ be the set of derivations producible from a phrase structure grammar $G$, whether proper or not. Let $D_F = \{ D(G) \mid G \mbox{ is a $[\Sigma, F]$ grammar}\}$ and $D_Q = \{D(G) \mid G \mbox{ is a proper grammars} \}$. Then $$ \mbox{$D_F$ and $D_Q$ are incomparable; i.e., $D_F\not\subseteq D_Q$ and $D_Q \not\subseteq D_F$}. $$

Where by a derivation he means every derivable string, even if they contain non-terminal symbols. And a $[\Sigma, F]$ grammar is a usual context-sensitive grammar with no restriction on rule application.

I do not understand why they are incomparable. For example if I have a (possibly non proper) grammar $G$ and make all rules obligatory, then certainly every derivation in $G$ applies in each step one obligatory rule, hence every derivation in $G$ is also a derivation in the proper variant of $G$, and as the other direction is clear both generate exactly the same set of derivable strings, hence $D_F \subseteq D_Q$???? Conversely I also cannot think of a set of string derivable by a proper grammar, for which there certainly exists no usual grammar?

$\endgroup$
  • $\begingroup$ F could be any set of rules. In other words, its obligatory list and optional list may not exactly match, nor complete, the list used to generate D(G) for proper grammar. $\endgroup$ – user457118 Jun 23 '17 at 3:59

Your Answer

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

Browse other questions tagged or ask your own question.