Formal language

related topics
{math, number, function}
{language, word, form}
{theory, work, human}

A formal language is a set of words, i.e. finite strings of letters, symbols, or tokens. The set from which these letters are taken is called the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar (also called its formation rules); accordingly, words that belong to a formal language are sometimes called well-formed words (or well-formed formulas). Formal languages are studied in computer science and linguistics; the field of formal language theory studies the purely syntactical aspects of such languages (that is, their internal structural patterns).

Formal languages are often used as the basis for richer constructs endowed with semantics. In computer science they are used, among other things, for the precise definition of data formats and the syntax of programming languages. Formal languages play a crucial role in the development of compilers, typically produced by means of a compiler compiler, which may be a single program or may be separated in tools like lexical analyzer generators (e.g. lex), and parser generators (e.g. yacc). Since formal languages alone do not have semantics, other formal constructs are needed for the formal specification of program semantics. Formal languages are also used in logic and in foundations of mathematics to represent the syntax of formal theories. Logical systems can be seen as a formal language with additional constructs, like proof calculi, which define a consequence relation.[1] "Tarski's definition of truth" in terms of a T-schema for first-order logic is an example of fully interpreted formal language; all its sentences have meanings that make them either true or false.

Contents

Full article ▸

related documents
Hungarian notation
Substitution cipher
Extended Backus–Naur Form
Reserved word
Grep
Pseudocode
Caesar cipher
Soundness
Multiplication table
Zorn's lemma
Local field
Arithmetic shift
Codomain
Linear cryptanalysis
Epimorphism
Mathematical singularity
Group isomorphism
Real analysis
Intermediate value theorem
P-complete
Distributivity
Five lemma
Dual number
Pointless topology
Tree (graph theory)
Nial
If and only if
Dedekind cut
Lambert W function
ZPP