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) » « Shrink index
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.
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.
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
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.
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.
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.
Arto K. Salomaa (born 6 June 1934) is a Finnish mathematician and computer scientist.
ASCII, abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication.
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.
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them.
Axel Thue (19 February 1863 – 7 March 1922), was a Norwegian mathematician, known for highly original work in diophantine approximation, and combinatorics.
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.
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.
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.
Bytecode, also termed portable code or p-code, is a form of instruction set designed for efficient execution by a software interpreter.
Cambridge University Press (CUP) is the publishing business of the University of Cambridge.
Character encoding is used to represent a repertoire of characters by some kind of encoding system.
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.
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.
Combinatorics on words is a fairly new field of mathematics, branching from combinatorics, which focuses on the study of words and formal languages.
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.
In set theory, the complement of a set refers to elements not in.
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
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.
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.
Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end.
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.
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.
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
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).
In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.
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.
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.
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages.
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.
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.
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.
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.
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.
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.
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.
A formal system is the name of a logic system usually defined in the mathematical way.
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.
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.
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.
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.
Friedrich Ludwig Gottlob Frege (8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician.
In linguistics, grammar (from Greek: γραμματική) is the set of structural rules governing the composition of clauses, phrases, and words in any given natural language.
Grzegorz Rozenberg (born 14 March 1942, Leninsk, Russia) is a Polish Dutch computer scientist.
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).
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.
An interpretation is an assignment of meaning to the symbols of a formal language.
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.
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.
Jeffrey David "Jeff" Ullman (born November 22, 1942) is an American computer scientist and professor at Stanford University.
John Edward Hopcroft (born October 7, 1939) is an American theoretical computer scientist.
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.
Lex is a computer program that generates lexical analyzers ("scanners" or "lexers").
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).
Linguistics is the scientific study of language, and involves an analysis of language form, language meaning, and language in context.
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.
Machine code is a computer program written in machine language instructions that can be executed directly by a computer's central processing unit (CPU).
Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics.
Mathematical notation is a system of symbolic representations of mathematical objects and ideas.
Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
Michael A. Harrison is a computer scientist, in particular a pioneer in the area of formal languages.
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.
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.
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").
The City of New York, often called New York City (NYC) or simply New York, is the most populous city in the United States.
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.
A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.
Proof theory is a major branchAccording to Wang (1981), pp.
The term proposition has a broad use in contemporary analytic philosophy.
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.
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.
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.
In theoretical computer science and formal language theory, a regular grammar is a formal grammar that is right-regular or left-regular.
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).
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".
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).
Semantics (from σημαντικός sēmantikós, "significant") is the linguistic and philosophical study of meaning, in language, programming languages, formal logics, and semiotics.
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.
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.
In mathematical logic, a sentence of a predicate logic is a boolean-valued well-formed formula with no free variables.
In mathematics, a set is a collection of distinct objects, considered as an object in its own right.
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.
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.
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.
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.
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.
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.
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.
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.
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth.
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.
Unicode is a computing industry standard for the consistent encoding, representation, and handling of text expressed in most of the world's writing systems.
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.
The University of Maryland, Baltimore, (also known as the University of Maryland or UMB) was founded in 1807.
In computing, a virtual machine (VM) is an emulation of a computer system.
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.
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson.
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).