Faster access than browser!
32 relations: Ambiguous grammar, Big O notation, Chomsky normal form, Circular shift, Closure (mathematics), Complement (complexity), Concatenation, Context-free grammar, Context-sensitive language, Coppersmith–Winograd algorithm, CYK algorithm, Deterministic context-free language, Deterministic pushdown automaton, Dyck language, Earley parser, Formal language, Intersection (set theory), Kleene star, LR parser, Matrix multiplication, Michael Sipser, Ogden's lemma, Parikh's theorem, Parsing, Parsing expression grammar, Programming language, Pumping lemma for context-free languages, Pushdown automaton, Regular language, Seymour Ginsburg, Undecidable problem, Union (set theory).
Ambiguous grammar
In computer science, an ambiguous grammar is a context-free grammar for which there exists a string that can have more than one leftmost derivation or parse tree, while an unambiguous grammar is a context-free grammar for which every valid string has a unique leftmost derivation or parse tree.
New!!: Context-free language and Ambiguous grammar · See more »
Big O notation
Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
New!!: Context-free language and Big O notation · See more »
Chomsky normal form
In formal language theory, a context-free grammar G is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form: where A, B, and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string.
New!!: Context-free language and Chomsky normal form · See more »
Circular shift
In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation.
New!!: Context-free language and Circular shift · 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!!: Context-free language and Closure (mathematics) · See more »
Complement (complexity)
In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers.
New!!: Context-free language and Complement (complexity) · See more »
Concatenation
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end.
New!!: Context-free language and Concatenation · 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!!: Context-free language and Context-free grammar · 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!!: Context-free language and Context-sensitive language · See more »
Coppersmith–Winograd algorithm
In linear algebra, the Coppersmith–Winograd algorithm, named after Don Coppersmith and Shmuel Winograd, was the asymptotically fastest known matrix multiplication algorithm until 2010.
New!!: Context-free language and Coppersmith–Winograd algorithm · See more »
CYK algorithm
In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami.
New!!: Context-free language and CYK algorithm · See more »
Deterministic context-free language
In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages.
New!!: Context-free language and Deterministic context-free language · See more »
Deterministic pushdown automaton
In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton.
New!!: Context-free language and Deterministic pushdown automaton · See more »
Dyck language
In the theory of formal languages of computer science, mathematics, and linguistics, a Dyck word is a balanced string of square brackets.
New!!: Context-free language and Dyck language · See more »
Earley parser
In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language, though (depending on the variant) it may suffer problems with certain nullable grammars.
New!!: Context-free language and Earley parser · 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!!: Context-free language and Formal language · 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!!: Context-free language and Intersection (set theory) · 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!!: Context-free language and Kleene star · See more »
LR parser
In computer science, LR parsers are a type of bottom-up parser that efficiently read deterministic context-free languages, in guaranteed linear time.
New!!: Context-free language and LR parser · See more »
Matrix multiplication
In mathematics, matrix multiplication or matrix product is a binary operation that produces a matrix from two matrices with entries in a field, or, more generally, in a ring or even a semiring.
New!!: Context-free language and Matrix multiplication · See more »
Michael Sipser
Michael Fredric Sipser (born September 17, 1954) is a theoretical computer scientist who has made early contributions to computational complexity theory.
New!!: Context-free language and Michael Sipser · See more »
Ogden's lemma
In the theory of formal languages, Ogden's lemma (named after William F. Ogden) is a generalization of the pumping lemma for context-free languages.
New!!: Context-free language and Ogden's lemma · See more »
Parikh's theorem
Parikh's theorem in theoretical computer science says that if one looks only at the number of occurrences of each terminal symbol in a context-free language, without regard to their order, then the language is indistinguishable from a regular language.
New!!: Context-free language and Parikh's theorem · See more »
Parsing
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!!: Context-free language and Parsing · See more »
Parsing expression grammar
In computer science, a parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.
New!!: Context-free language and Parsing expression grammar · 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!!: Context-free language and Programming language · See more »
Pumping lemma for context-free languages
In computer science, in particular in formal language theory, the pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages and generalizes the pumping lemma for regular languages.
New!!: Context-free language and Pumping lemma for context-free languages · See more »
Pushdown automaton
In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.
New!!: Context-free language and Pushdown automaton · 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!!: Context-free language and Regular language · 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!!: Context-free language and Seymour Ginsburg · See more »
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.
New!!: Context-free language and Undecidable problem · 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!!: Context-free language and Union (set theory) · See more »
Redirects here:
Context Free Languages, Context free language, Context-Free Language, Context-Free languages, Context-free, Context-free languages.
References
[1] https://en.wikipedia.org/wiki/Context-free_language
