Formal language

From TCS Wiki
Revision as of 00:57, 25 February 2017 by 61.6.239.245 (talk) (Fixed typo, Fixed grammar, Added links)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Language

Examples

Some examples of formal languages:

  • the set of all words over [math]\displaystyle{ {a, b}\, }[/math]
  • the set [math]\displaystyle{ \left \{ a^{n}\right\} }[/math], where [math]\displaystyle{ n\, }[/math] is a natural number and [math]\displaystyle{ a^n\, }[/math] means [math]\displaystyle{ a\, }[/math] repeated [math]\displaystyle{ n\, }[/math] times
  • finite languages, such as [math]\displaystyle{ \{\{a,b\},\{a, aa, bba\}\}\, }[/math]
  • the set of syntactically correct programs in a given programming language; or
  • the set of inputs upon which a certain Turing machine halts.

Specification

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

Other pages

Further reading

Other websites