Formal language

formal language theoryformal languageslanguagesymbolic systemlanguagesformalformal modelsymbolic meaningformalizeinformal
In mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.wikipedia
570 Related Articles

Alphabet (formal languages)

alphabetalphabetsinput symbol
In mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
In formal language theory, a string is defined as a finite sequence of members of an underlying base set; this set is called the alphabet of a string or collection of strings.

Formal grammar

grammarformal grammarsgrammars
A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules. Axel Thue's early semi-Thue system, which can be used for rewriting strings, was influential on formal grammars.
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) is a set of production rules for strings in a formal language.

String (computer science)

stringstringscharacter string
In mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set called an alphabet.

Context-free grammar

context-free grammarscontext-freecontext free grammar
A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules.
In formal language theory, a context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language.

Symbol (formal)

symbolsymbolsletters
In mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
Although the term "symbol" in common use refers at some times to the idea being symbolized, and at other times to the marks on a piece of paper or chalkboard which are being used to express that idea; in the formal languages studied in mathematics and logic, the term "symbol" refers to the idea, and the marks are considered to be a token instance of the symbol.

Syntax

syntacticsyntacticalsyntactically
The field of formal language theory studies primarily the purely syntactical aspects of such languages—that is, their internal structural patterns.
In mathematics, syntax refers to the rules governing the notation of mathematical systems, such as formal languages used in logic.

Programming language

programming languageslanguagedialect
In computer science, formal languages are used among others as the basis for defining the grammar of programming languages and formalized versions of subsets of natural languages in which the words of the language represent concepts that are associated with particular meanings or semantics.
A programming language is a formal language, which comprises a set of instructions used to produce various kinds of output.

Well-formed formula

formulaformulaswell-formed
Each string concatenated from symbols of this alphabet is called a word, and the words that belong to a particular formal language are sometimes called well-formed words or well-formed formulas.
In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language.

Regular grammar

Regular(right) regular (string) grammarregular (or Type-3) grammars
A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules.
In theoretical computer science and formal language theory, a regular grammar is a formal grammar that is right-regular or left-regular.

Formation rule

term
A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules.
In mathematical logic, formation rules are rules for describing which strings of symbols formed from the alphabet of a formal language are syntactically valid within the language.

Computational complexity theory

computational complexitycomplexity theorycomplexity
In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines with limited computational power. Therefore, formal language theory is a major application area of computability theory and complexity theory.
A decision problem can be viewed as a formal language, where the members of the language are instances whose output is yes, and the non-members are those instances whose output is no. The objective is to decide, with the aid of an algorithm, whether a given input string is a member of the formal language under consideration.

Natural language

linguisticnaturalnatural languages
Formal language theory sprang out of linguistics, as a way of understanding the syntactic regularities of natural languages.
They are distinguished from constructed and formal languages such as those used to program computers or to study logic.

Concatenation

concatenatedconcatenateconcatenating
By concatenation one can combine two words to form a new word, whose length is the sum of the lengths of the original words.
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end.

Decision problem

undecidabledecision problemsdecision procedure
In computational complexity theory, decision problems are typically defined as formal languages, and complexity classes are defined as the sets of the formal languages that can be parsed by machines with limited computational power.
The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined as formal languages.

Regular language

regularregular languagesREG
In practice, there are many languages that can be described by rules, such as regular languages or context-free languages.
In theoretical computer science and formal language theory, a regular language (also called a rational language ) is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science (as opposed to many regular expressions engines provided by modern programming languages, which are augmented with features that allow recognition of languages that cannot be expressed by a classic regular expression).

Chomsky hierarchy

Chomsky (1956) hierarchyChomsky grammarsChomsky Languages
Formal languages may be classified in the Chomsky hierarchy based on the expressive power of their generative grammar as well as the complexity of their recognizing automaton.
In the formal languages of computer science and linguistics, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars.

Computer science

computer scientistcomputer sciencescomputer scientists
In mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particular logic calculi, formal languages, automata theory, and program semantics, but also type systems and algebraic data types to problems in software and hardware specification and verification.

Computability theory

recursion theorycomputablecomputability
Therefore, formal language theory is a major application area of computability theory and complexity theory.
Although there is considerable overlap in terms of knowledge and methods, mathematical recursion theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages.

Semi-Thue system

string rewriting systemsemi-Thue grammarword problem for semigroups
Axel Thue's early semi-Thue system, which can be used for rewriting strings, was influential on formal grammars.
, sometimes called words in formal languages; we will simply call them strings here.

Automata theory

automataautomatontheory of automata
Formal languages may be classified in the Chomsky hierarchy based on the expressive power of their generative grammar as well as the complexity of their recognizing automaton. those strings accepted by some automaton, such as a Turing machine or finite state automaton;
Automata theory is closely related to formal language theory.

Context-free language

context-freecontext-free languagescontext free language
In practice, there are many languages that can be described by rules, such as regular languages or context-free languages.
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).

Cone (formal languages)

conefull triotrios
The theory of trios and abstract families of languages studies the most common closure properties of language families in their own right.
In formal language theory, a cone is a set of formal languages that has some desirable closure properties enjoyed by some well-known sets of languages, in particular by the families of regular languages, context-free languages and the recursively enumerable languages.

Deterministic context-free language

DCFLdeterministicdeterministic context-free languages
! DCFL
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages.

Indexed language

INDindexed languages
! IND
Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automata.

Abstract family of languages

AFL Theoryabstract families of languagestrio
The theory of trios and abstract families of languages studies the most common closure properties of language families in their own right.
In computer science, in particular in the field of formal language theory,