Formal language

set of strings of symbols that may be constrained by rules that are specific to it; words whose letters are taken from an alphabet and are well-formed according to a specific set of rules

In mathematics, a formal language is one that has a particular set of symbols that are made according to a particular kind of rule.

ExamplesEdit

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.

SpecificationEdit

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

Related pagesEdit

Further readingEdit

  • Hopcroft, J. & Ullman, J. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.CS1 maint: multiple names: authors list (link)
  • Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics (3rd ed. ed.). PWN.CS1 maint: extra text (link), 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.CS1 maint: multiple names: authors list (link) CS1 maint: extra text: authors list (link)

Other websitesEdit