Generate

From Glottopedia
Jump to navigation Jump to search

Generate is a set of rules is said to generate a string or a structure if a finite sequence of applications of those rules will result in the string or structure as output.

Example

a rewrite grammar, consisting of a start symbol, a set of auxiliary symbols, a set of terminal symbols, and a set of rewrite rules is said to generate those sentences or structures that can be arrived at through a finite succession of applications of those rewrite rules starting with applying a rule to the start symbol and each successive rule being applied to the output of the former, until no auxiliary symbols remain. The classes of structures that rules of a given type can generate define the strong generative capacity of that type; the classes of strings that rules of a given type can generate define the weak generative capacity of that type. See Phrase structure rules. In actual practice the term 'generate' has become equivalent to 'characterize explicitly'.

Link

Utrecht Lexicon of Linguistics

References

  • Brandt Corstius, H. 1974. Algebraische taalkunde, Oosthoek, Utrecht.
  • Chomsky, N. 1963. Formal Properties of grammar, in: R.D. e.a. (eds.) Handbook of mathematical psychology, Wiley, New York.
  • Hopcroft&Ullman 1969. Formal languages and their relations to automata., Addison-Wesley:Reading Mass.