Formal language

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Language

Examples[change | change source]

Some examples of formal languages:

  • the set of all words over
  • the set , where is a natural number and means repeated times
  • finite languages, such as
  • the set of syntactically correct programs in a given programming language; or
  • the set of inputs upon which a certain Turing machine halts.

Specification[change | change source]

A formal language can be specified in a great variety of ways, such as:


Other pages[change | change source]

Further reading[change | change source]

  • Hopcroft, J. & Ullman, J. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. 
  • Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics (3rd ed. ed.). PWN.  , chapter 6 Algebra of formalized languages.
  • Rozemberg, G. & Salomaa, A. (eds.) (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-3-540-61486-9. 

Other websites[change | change source]