Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Formal language

Index Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it. [1]

103 relations: Abstract family of languages, Abstract syntax tree, Algorithm, Alphabet, Alphabet (formal languages), Alphanumeric, Arto Salomaa, ASCII, Associative array, Automata theory, Axel Thue, Axiom, Axiomatic system, Begriffsschrift, Bytecode, Cambridge University Press, Character encoding, Chomsky hierarchy, Closure (mathematics), Combinatorics on words, Compiler-compiler, Complement (set theory), Complexity class, Computability theory, Computational complexity theory, Computer science, Concatenation, Cone (formal languages), Context-free grammar, Context-free language, Context-sensitive language, Countable set, Decision problem, Degeneracy (mathematics), Deterministic context-free language, Empty set, Executable, Finite-state machine, First-order logic, Formal grammar, Formal language, Formal methods, Formal system, Formalism (philosophy of mathematics), Formation rule, Foundations of mathematics, Free monoid, Gottlob Frege, Grammar, Grzegorz Rozenberg, ..., Identifier, Indexed language, Interpretation (logic), Intersection (set theory), Introduction to Automata Theory, Languages, and Computation, Jeffrey Ullman, John Hopcroft, Kleene star, Lex (software), Lexical analysis, Linguistics, Logic, Machine code, Mathematical logic, Mathematical notation, Mathematics, Michael A. Harrison, Model theory, Natural language, Natural number, New York City, Parsing, Programming language, Proof theory, Proposition, Recursive language, Recursively enumerable language, Regular expression, Regular grammar, Regular language, Reserved word, Rule of inference, Semantics, Semantics of logic, Semi-Thue system, Sentence (mathematical logic), Set (mathematics), Seymour Ginsburg, Springer Science+Business Media, String (computer science), String operations, Structure (mathematical logic), Subset, Symbol (formal), Syntax, Truth value, Turing machine, Unicode, Union (set theory), University of Maryland, Baltimore, Virtual machine, Well-formed formula, Yacc. Expand index (53 more) »

Abstract family of languages

In computer science, in particular in the field of formal language theory, the term abstract family of languages refers to an abstract mathematical notion generalizing characteristics common to the regular languages, the context-free languages and the recursively enumerable languages, and other families of formal languages studied in the scientific literature.

New!!: Formal language and Abstract family of languages · See more »

Abstract syntax tree

In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language.

New!!: Formal language and Abstract syntax tree · See more »


In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: Formal language and Algorithm · See more »


An alphabet is a standard set of letters (basic written symbols or graphemes) that is used to write one or more languages based upon the general principle that the letters represent phonemes (basic significant sounds) of the spoken language.

New!!: Formal language and Alphabet · See more »

Alphabet (formal languages)

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.

New!!: Formal language and Alphabet (formal languages) · See more »


Alphanumeric is a combination of alphabetic and numeric characters, and is used to describe the collection of Latin letters and Arabic digits or a text constructed from this collection.

New!!: Formal language and Alphanumeric · See more »

Arto Salomaa

Arto K. Salomaa (born 6 June 1934) is a Finnish mathematician and computer scientist.

New!!: Formal language and Arto Salomaa · See more »


ASCII, abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication.

New!!: Formal language and ASCII · See more »

Associative array

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

New!!: Formal language and Associative array · See more »

Automata theory

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them.

New!!: Formal language and Automata theory · See more »

Axel Thue

Axel Thue (19 February 1863 – 7 March 1922), was a Norwegian mathematician, known for highly original work in diophantine approximation, and combinatorics.

New!!: Formal language and Axel Thue · See more »


An axiom or postulate is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments.

New!!: Formal language and Axiom · See more »

Axiomatic system

In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems.

New!!: Formal language and Axiomatic system · See more »


Begriffsschrift (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book.

New!!: Formal language and Begriffsschrift · See more »


Bytecode, also termed portable code or p-code, is a form of instruction set designed for efficient execution by a software interpreter.

New!!: Formal language and Bytecode · See more »

Cambridge University Press

Cambridge University Press (CUP) is the publishing business of the University of Cambridge.

New!!: Formal language and Cambridge University Press · See more »

Character encoding

Character encoding is used to represent a repertoire of characters by some kind of encoding system.

New!!: Formal language and Character encoding · See more »

Chomsky hierarchy

In the formal languages of computer science and linguistics, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.

New!!: Formal language and Chomsky hierarchy · See more »

Closure (mathematics)

A set has closure under an operation if performance of that operation on members of the set always produces a member of the same set; in this case we also say that the set is closed under the operation.

New!!: Formal language and Closure (mathematics) · See more »

Combinatorics on words

Combinatorics on words is a fairly new field of mathematics, branching from combinatorics, which focuses on the study of words and formal languages.

New!!: Formal language and Combinatorics on words · See more »


In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine.

New!!: Formal language and Compiler-compiler · See more »

Complement (set theory)

In set theory, the complement of a set refers to elements not in.

New!!: Formal language and Complement (set theory) · See more »

Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.

New!!: Formal language and Complexity class · See more »

Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

New!!: Formal language and Computability theory · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Formal language and Computational complexity theory · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Formal language and Computer science · See more »


In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end.

New!!: Formal language and Concatenation · See more »

Cone (formal languages)

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.

New!!: Formal language and Cone (formal languages) · See more »

Context-free grammar

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.

New!!: Formal language and Context-free grammar · See more »

Context-free language

In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).

New!!: Formal language and Context-free language · See more »

Context-sensitive language

In formal language theory, a context-sensitive language is a language that can be defined by a context-sensitive grammar (and equivalently by a noncontracting grammar).

New!!: Formal language and Context-sensitive language · See more »

Countable set

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

New!!: Formal language and Countable set · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: Formal language and Decision problem · See more »

Degeneracy (mathematics)

In mathematics, a degenerate case is a limiting case in which an element of a class of objects is qualitatively different from the rest of the class and hence belongs to another, usually simpler, class.

New!!: Formal language and Degeneracy (mathematics) · See more »

Deterministic context-free language

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

New!!: Formal language and Deterministic context-free language · See more »

Empty set

In mathematics, and more specifically set theory, the empty set or null set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero.

New!!: Formal language and Empty set · See more »


In computing, executable code or an executable file or executable program, sometimes simply referred to as an executable or binary, causes a computer "to perform indicated tasks according to encoded instructions," as opposed to a data file that must be parsed by a program to be meaningful.

New!!: Formal language and Executable · See more »

Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

New!!: Formal language and Finite-state machine · See more »

First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

New!!: Formal language and First-order logic · See more »

Formal grammar

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.

New!!: Formal language and Formal grammar · See more »

Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.

New!!: Formal language and Formal language · See more »

Formal methods

In computer science, specifically software engineering and hardware engineering, formal methods are a particular kind of mathematically based techniques for the specification, development and verification of software and hardware systems.

New!!: Formal language and Formal methods · See more »

Formal system

A formal system is the name of a logic system usually defined in the mathematical way.

New!!: Formal language and Formal system · See more »

Formalism (philosophy of mathematics)

In foundations of mathematics, philosophy of mathematics, and philosophy of logic, formalism is a theory that holds that statements of mathematics and logic can be considered to be statements about the consequences of certain string manipulation rules.

New!!: Formal language and Formalism (philosophy of mathematics) · See more »

Formation rule

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.

New!!: Formal language and Formation rule · See more »

Foundations of mathematics

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics.

New!!: Formal language and Foundations of mathematics · See more »

Free monoid

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element.

New!!: Formal language and Free monoid · See more »

Gottlob Frege

Friedrich Ludwig Gottlob Frege (8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician.

New!!: Formal language and Gottlob Frege · See more »


In linguistics, grammar (from Greek: γραμματική) is the set of structural rules governing the composition of clauses, phrases, and words in any given natural language.

New!!: Formal language and Grammar · See more »

Grzegorz Rozenberg

Grzegorz Rozenberg (born 14 March 1942, Leninsk, Russia) is a Polish Dutch computer scientist.

New!!: Formal language and Grzegorz Rozenberg · See more »


An identifier is a name that identifies (that is, labels the identity of) either a unique object or a unique class of objects, where the "object" or class may be an idea, physical object (or class thereof), or physical substance (or class thereof).

New!!: Formal language and Identifier · See more »

Indexed language

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.

New!!: Formal language and Indexed language · See more »

Interpretation (logic)

An interpretation is an assignment of meaning to the symbols of a formal language.

New!!: Formal language and Interpretation (logic) · See more »

Intersection (set theory)

In mathematics, the intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.

New!!: Formal language and Intersection (set theory) · See more »

Introduction to Automata Theory, Languages, and Computation

Introduction to Automata Theory, Languages, and Computation is an influential computer science textbook by John Hopcroft and Jeffrey Ullman on formal languages and the theory of computation.

New!!: Formal language and Introduction to Automata Theory, Languages, and Computation · See more »

Jeffrey Ullman

Jeffrey David "Jeff" Ullman (born November 22, 1942) is an American computer scientist and professor at Stanford University.

New!!: Formal language and Jeffrey Ullman · See more »

John Hopcroft

John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist.

New!!: Formal language and John Hopcroft · See more »

Kleene star

In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters.

New!!: Formal language and Kleene star · See more »

Lex (software)

Lex is a computer program that generates lexical analyzers ("scanners" or "lexers").

New!!: Formal language and Lex (software) · See more »

Lexical analysis

In computer science, lexical analysis, lexing or tokenization is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of tokens (strings with an assigned and thus identified meaning).

New!!: Formal language and Lexical analysis · See more »


Linguistics is the scientific study of language, and involves an analysis of language form, language meaning, and language in context.

New!!: Formal language and Linguistics · See more »


Logic (from the logikḗ), originally meaning "the word" or "what is spoken", but coming to mean "thought" or "reason", is a subject concerned with the most general laws of truth, and is now generally held to consist of the systematic study of the form of valid inference.

New!!: Formal language and Logic · See more »

Machine code

Machine code is a computer program written in machine language instructions that can be executed directly by a computer's central processing unit (CPU).

New!!: Formal language and Machine code · See more »

Mathematical logic

Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.

New!!: Formal language and Mathematical logic · See more »

Mathematical notation

Mathematical notation is a system of symbolic representations of mathematical objects and ideas.

New!!: Formal language and Mathematical notation · See more »


Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

New!!: Formal language and Mathematics · See more »

Michael A. Harrison

Michael A. Harrison is a computer scientist, in particular a pioneer in the area of formal languages.

New!!: Formal language and Michael A. Harrison · See more »

Model theory

In mathematics, model theory is the study of classes of mathematical structures (e.g. groups, fields, graphs, universes of set theory) from the perspective of mathematical logic.

New!!: Formal language and Model theory · See more »

Natural language

In neuropsychology, linguistics, and the philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation.

New!!: Formal language and Natural language · See more »

Natural number

In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country").

New!!: Formal language and Natural number · See more »

New York City

The City of New York, often called New York City (NYC) or simply New York, is the most populous city in the United States.

New!!: Formal language and New York City · See more »


Parsing, syntax analysis or syntactic analysis is the process of analysing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

New!!: Formal language and Parsing · See more »

Programming language

A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.

New!!: Formal language and Programming language · See more »

Proof theory

Proof theory is a major branchAccording to Wang (1981), pp.

New!!: Formal language and Proof theory · See more »


The term proposition has a broad use in contemporary analytic philosophy.

New!!: Formal language and Proposition · See more »

Recursive language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

New!!: Formal language and Recursive language · See more »

Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

New!!: Formal language and Recursively enumerable language · See more »

Regular expression

A regular expression, regex or regexp (sometimes called a rational expression) is, in theoretical computer science and formal language theory, a sequence of characters that define a search pattern.

New!!: Formal language and Regular expression · See more »

Regular grammar

In theoretical computer science and formal language theory, a regular grammar is a formal grammar that is right-regular or left-regular.

New!!: Formal language and Regular grammar · See more »

Regular language

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).

New!!: Formal language and Regular language · See more »

Reserved word

In a computer language, a reserved word (also known as a reserved identifier) is a word that cannot be used as an identifier, such as the name of a variable, function, or label – it is "reserved from use".

New!!: Formal language and Reserved word · See more »

Rule of inference

In logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, analyzes their syntax, and returns a conclusion (or conclusions).

New!!: Formal language and Rule of inference · See more »


Semantics (from σημαντικός sēmantikós, "significant") is the linguistic and philosophical study of meaning, in language, programming languages, formal logics, and semiotics.

New!!: Formal language and Semantics · See more »

Semantics of logic

In logic, the semantics of logic is the study of the semantics, or interpretations, of formal and (idealizations of) natural languages usually trying to capture the pre-theoretic notion of entailment.

New!!: Formal language and Semantics of logic · See more »

Semi-Thue system

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet.

New!!: Formal language and Semi-Thue system · See more »

Sentence (mathematical logic)

In mathematical logic, a sentence of a predicate logic is a boolean-valued well-formed formula with no free variables.

New!!: Formal language and Sentence (mathematical logic) · See more »

Set (mathematics)

In mathematics, a set is a collection of distinct objects, considered as an object in its own right.

New!!: Formal language and Set (mathematics) · See more »

Seymour Ginsburg

Seymour Ginsburg (December 12, 1927 – December 5, 2004) was an American pioneer of automata theory, formal language theory, and database theory, in particular; and computer science, in general.

New!!: Formal language and Seymour Ginsburg · See more »

Springer Science+Business Media

Springer Science+Business Media or Springer, part of Springer Nature since 2015, is a global publishing company that publishes books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.

New!!: Formal language and Springer Science+Business Media · See more »

String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

New!!: Formal language and String (computer science) · See more »

String operations

In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming.

New!!: Formal language and String operations · See more »

Structure (mathematical logic)

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

New!!: Formal language and Structure (mathematical logic) · See more »


In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

New!!: Formal language and Subset · See more »

Symbol (formal)

A logical symbol is a fundamental concept in logic, tokens of which may be marks or a configuration of marks which form a particular pattern.

New!!: Formal language and Symbol (formal) · See more »


In linguistics, syntax is the set of rules, principles, and processes that govern the structure of sentences in a given language, usually including word order.

New!!: Formal language and Syntax · See more »

Truth value

In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth.

New!!: Formal language and Truth value · See more »

Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: Formal language and Turing machine · See more »


Unicode is a computing industry standard for the consistent encoding, representation, and handling of text expressed in most of the world's writing systems.

New!!: Formal language and Unicode · See more »

Union (set theory)

In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.

New!!: Formal language and Union (set theory) · See more »

University of Maryland, Baltimore

The University of Maryland, Baltimore, (also known as the University of Maryland or UMB) was founded in 1807.

New!!: Formal language and University of Maryland, Baltimore · See more »

Virtual machine

In computing, a virtual machine (VM) is an emulation of a computer system.

New!!: Formal language and Virtual machine · See more »

Well-formed formula

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.

New!!: Formal language and Well-formed formula · See more »


Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson.

New!!: Formal language and Yacc · See more »

Redirects here:

Applications of formal language theory, Complement of a language, Concatenation of languages, Empty language, Formal expression, Formal language theory, Formal languages, Formal linguistic analysis, Formal model, Language (computability), Language (computer science), Language (logic), Language (mathematical logic), Language (mathematics), Operations on languages, Symbolic meaning, Symbolic system, Word (formal languages).


[1] https://en.wikipedia.org/wiki/Formal_language

Hey! We are on Facebook now! »