Comment on the paper “Error detection in formal languages”

✍ Scribed by György Révész

• Publisher: Elsevier Science
• Year: 1974
• Tongue: English
• Weight: 161 KB
• Volume: 8
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(74)80057-7

✦ Synopsis

In a paper of W. B. Smith [1], some normal form theorems have been presented about context-sensitive grammars. Professor A. Salomaa has noticed that the proof of Lemma 2 in this paper was incorrect and he has given an example in which the proof does not work. 1 It was guessed that there was no simple way to repair Smith's proof, while M. Penttonen has found a rather complicated proof of a somewhat stronger normal form [2].

We shall give here a construction that is quite simple and still works. Before doing so, we must mention that the proof of Lemma 1 in Smith's paper is also incorrect and a similar bug can be found also in the well-known paper of Kuroda [3]: namely, on page 211 of the latter it is stated that each rule AB--~CD of a contextsensitive grammar can be replaced by three rules: AB--~A'B, A'B---~ A'D and A'D --+ CD where A' is a new non-terminal symbol. Consider, however, the following rules: S --~ AB, B ~ DE, AB ~ CD. The above replacement yields a set of rules permitting a derivation S *~ CDE which does not exist in the original grammar. In order to avoid this parasitical derivation we have to apply four rules: AB ~ A'B, A'B-+ A'B', A'B' --~ CB' and CB' ~ CD, where A' and B' are new non-terminal symbols.

The situation is more complex in the case of Smith's proofs.

LEM~A 1 asserts that any language generated by a left-context-sensitive grammar G can be generated by some grammar G' all of whose rules are of the form A --~ a, A --~ BC or BA --~ BC, where A, B, C are non-terminals and a is terminal.