Noncontracting grammar

In formal language theory, a grammar is noncontracting (or monotonic) if all of its production rules are of the form α → β where α and β are strings of nonterminal and terminal symbols, and the length of α is less than or equal to that of β, |α| ≤ |β|, that is β is not shorter than α. A grammar is essentially noncontracting if there may be one exception, namely, a rule S → ε where S is the start symbol and ε the empty string, and furthermore, S never occurs in the right-hand side of any rule.

None of the rules of a noncontracting grammar decreases the length of the string that is being rewritten. If each rule even properly increases the length, the grammar is called a growing context-sensitive grammar.

History

Chomsky (1963) called a noncontracting grammar a type 1 grammar; in the same work, he called a context-sensitive grammar a "type 2 grammar", and he proved that these two are weakly equivalent (context-free grammars were designated "type 4" in this work).[1] The type numbering scheme in this 1963 work of Chomsky does not coincide with the earlier one known today as the Chomsky hierarchy because he was trying to emphasize the distinction between weak [generative] and strong [structural] equivalence; in his 1959 work he had used "type 1 grammar" to denote a context-sensitive grammar and "type 2" for context-free.[2][3]

Example

S → abc
S → aSBc
cB → Bc
bB → bb

This grammar, with the start symbol S, generates the language { anbncn : n ≥ 1 },[4] which is not context-free due to the pumping lemma.

A context-sensitive grammar for the same language is shown below.

Transforming into context-sensitive grammar

Every noncontracting grammar (N, Σ, P, S) can be transformed into a context-sensitive grammar (N’, Σ, P’, S) as follows:

  1. For every terminal symbol a ∈ Σ, introduce a new nonterminal symbol [a] ∈ N’, and a new rule ([a] → a) ∈ P’.
  2. In the rules of P, replace every terminal symbol a by its corresponding nonterminal symbol [a]. As a result, all these rules are of the form X1...Xm → Y1...Yn for nonterminals Xi, Yj and m≤n.
  3. Replace each rule X1...Xm → Y1...Yn with m>1 by 2m rules:[note 1]
X1 X2 ... Xm-1 Xm → Z1 X2 ... Xm-1 Xm
Z1 X2 ... Xm-1 Xm → Z1 Z2 ... Xm-1 Xm
 :
Z1 Z2 ... Xm-1 Xm → Z1 Z2 ... Zm-1 Xm
Z1 Z2 ... Zm-1 Xm → Z1 Z2 ... Zm-1 Zm Ym+1 ... Yn
Z1 Z2 ... Zm-1 Zm Ym+1 ... Yn       →       Y1 Z2 ... Zm-1 Zm Ym+1 ... Yn
Y1 Z2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Y2 ... Zm-1 Zm Ym+1 ... Yn
 :
Y1 Y2 ... Zm-1 Zm Ym+1 ... Yn → Y1 Y2 ... Ym-1 Zm Ym+1 ... Yn
Y1 Y2 ... Ym-1 Zm Ym+1 ... Yn → Y1 Y2 ... Ym-1 Ym Ym+1 ... Yn
where each Zi ∈ N’ is a new nonterminal not occurring elsewhere.[5][6]

For example, the above noncontracting grammar for { anbncn | n ≥ 1 } leads to the following context-sensitive grammar (with start symbol S) for the same language:

[a] → a from step 1
[b] → b from step 1
[c] → c from step 1
S → [a] [b] [c] from step 2, unchanged
S → [a] S B [c]       from step 2, unchanged
[c] B → B [c] from step 2, further modified below
[c] B → Z1 B modified from above in step 3
Z1 B → Z1 Z2 modified from above in step 3
Z1 Z2       →       B Z2 modified from above in step 3
B Z2 → B [c] modified from above in step 3
[b] B → [b] [b] from step 2, further modified below
[b] B → Z3 B modified from above in step 3
Z3 B → Z3 Z4 modified from above in step 3
Z3 Z4 → [b] Z4 modified from above in step 3
[b] Z4 → [b] [b] modified from above in step 3

Expressive power

Similarly, there is an easy procedure for bringing any noncontracting grammar into Kuroda normal form.[7][8] Vice versa, every context-sensitive grammar and every Kuroda normal form grammar is trivially also a noncontracting grammar. Therefore, noncontracting grammars, grammars in Kuroda normal form, and context-sensitive grammars have the same expressive power. To be precise, the noncontracting grammars describe exactly the context-sensitive languages that do not include the empty string, while the essentially noncontracting grammars describe exactly the set of context-sensitive languages.

See also

Notes

  1. ↑ For convenience, the non-context part of left and right hand side is shown in boldface.

References

  1. ↑ Chomsky, N. 1963. Formal properties of grammar. Handbook of Mathematical Psychology. R.D. Luce, R.R. Bush, & E. Galanter (eds), New York: Wiley. pp. 360-363 and 367
  2. ↑ Chomsky, N. 1959a. On certain formal properties of grammars. Information and Control 2: 137–67. (141-42 for the definitions)
  3. ↑ Willem J. M. Levelt (2008). An Introduction to the Theory of Formal Languages and Automata. John Benjamins Publishing. pp. 125–126. ISBN 90-272-3250-4.
  4. ↑ Mateescu & Salomaa (1997), Example 2.1, p. 188
  5. ↑ Mateescu & Salomaa (1997), Theorem 2.1, p. 187
  6. ↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Exercise 9.9, p.230. In the 2003 edition, the chapter on noncontracting / context-sensitive languages has been omitted.
  7. ↑ Sige-Yuki Kuroda (June 1964). "Classes of languages and linear-bounded automata". Information and Control 7 (2): 207–223. doi:10.1016/s0019-9958(64)90120-2.
  8. ↑ Mateescu & Salomaa (1997), Theorem 2.2, p. 190

This article is issued from Wikipedia - version of the Saturday, August 29, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.