Editing Formal language (section)

{{Short description|Sequence of words formed by specific rules}}
{{About|a technical term in mathematics and computer science|any formal type of language usage|Literary language| studies about natural languages|Formal semantics (natural language)}}
{{More citations needed|date=March 2024}}
{{Formal languages}}
{{Use dmy dates|date=November 2023}}
[[File:Syntax tree.svg|thumb|upright=1.15|Structure of the syntactically well-formed, although thoroughly nonsensical, English sentence, ''"Colorless green ideas sleep furiously"'' ([[Colorless green ideas sleep furiously|historical example]] from [[Chomsky]] 1957)]]
In [[logic]], [[mathematics]], [[computer science]], and [[linguistics]], a '''formal language''' is a set of [[string (computer science)|strings]] whose symbols are taken from a set called "[[#Definition|alphabet]]".

The alphabet of a formal language consists of symbols that concatenate into strings (also called "words").<ref>See e.g. {{cite book|title=Formal Languages and Compilation|series=Texts in Computer Science|first=Stefano Crespi|last=Reghizzi|publisher=Springer|year=2009|isbn=9781848820500|page=8 |bibcode=2009flc..book.....C|quote=An alphabet is a finite set |url=https://books.google.com/books?id=AxH6cWm61i0C}}</ref> Words that belong to a particular formal language are sometimes called [[Formal language#Definition|''well-formed words'']]. A formal language is often defined by means of a [[formal grammar]] such as a [[regular grammar]] or [[context-free grammar]].

In computer science, formal languages are used, among others, as the basis for defining the grammar of [[programming language]]s and formalized versions of subsets of natural languages, in which the words of the language represent concepts that are associated with meanings or [[semantics]]. In [[computational complexity theory]], [[decision problem]]s are typically defined as formal languages, and [[complexity class]]es are defined as the sets of the formal languages that can be [[Parsing|parsed by machines]] with limited computational power. In [[logic]] and the [[foundations of mathematics]], formal languages are used to represent the syntax of [[axiomatic system]]s, and [[Formalism (philosophy of mathematics)|mathematical formalism]] is the philosophy that all of mathematics can be reduced to the syntactic manipulation of formal languages in this way.

The field of '''formal language theory''' studies primarily the purely [[syntactic]] aspects of such languages—that is, their internal structural patterns. Formal language theory sprang out of linguistics, as a way of understanding the syntactic regularities of [[natural language]]s.