# 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**

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,