Formal language

From Simple English Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, computer science and linguistics, a formal language is one that has a particular set of symbols, and whose expressions are made according to a particular set of rules. The symbol is often used as a variable for formal languages in logic.[1]

Unlike natural languages, the symbols and formulas in formal languages are syntactically and semantically related to one another in a precise way.[2] As a result, formal languages are completely (or almost completely) void of ambiguity.[3]

Examples[change | change source]

Some examples of formal languages include:

  • 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
  • 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:

Related pages[change | change source]

References[change | change source]

  1. "Comprehensive List of Logic Symbols". Math Vault. 2020-04-06. Retrieved 2020-10-09.
  2. "Definition of formal language |". Retrieved 2020-10-09.
  3. "1.11. Formal and Natural Languages — How to Think like a Computer Scientist: Interactive Edition". Retrieved 2020-10-09.

Further reading[change | change source]

  • 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 websites[change | change source]