Discover published sets by community

The Pumping Lemma for Regular Languages is a property that states that all sufficiently long words of a regular language can be pumped (i.e., have a middle section of the word repeated an arbitrary number of times) and still belong to the language.

Grammar derivation is the process of producing a string from the start symbol by repeatedly applying the production rules of a grammar.

Recursive languages are types of formal languages for which there exist a Turing Machine that will always halt and accept the string if it belongs to the language. Recursively enumerable languages are those for which a Turing Machine exists that will halt and accept when a string belongs to the language, but may not halt if the string does not.

A deterministic finite automaton is a type of automaton where for each state and input symbol, there is exactly one next state.

A finite automaton is a theoretical machine used in formal language theory that has a limited set of states, transitions between states, and can accept or reject strings of symbols.

A context-free grammar (CFG) is a set of recursive rewriting rules used to generate patterns of strings. It consists of a set of production rules that describe all possible strings in a given formal language.

An unambiguous grammar is a type of context-free grammar for which every word in the language has a unique leftmost (or rightmost) derivation.

A Pushdown Automaton (PDA) is a type of automaton that can make use of a stack data structure, thereby recognizing Context-Free Languages (CFLs).

Closure properties of languages refer to the ability to combine languages in certain ways to produce another language of the same class. For instance, regular languages are closed under union, concatenation, and Kleene star.

The Chomsky Hierarchy is a containment hierarchy of classes of formal grammars that generate formal languages. It categorizes grammars into types 0 through 3.

A non-deterministic finite automaton is an automaton where for some state and input symbol, there may be several possible next states.

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

The Kleene Star is an operation on sets of strings that forms the smallest regular language containing the original set. For a set $A$, the Kleene Star is the set $A^*$, which includes all strings of zero or more concatenations of strings from $A$.

A regular expression is a sequence of characters that defines a search pattern, mainly for the use in pattern matching with strings, or string matching.