Formal Language Theory¶

← Back to Domain-Specific Abstractions by Domain

11 domain-specific abstractions whose origin domain is Formal Language Theory.

Chomsky hierarchy — A containment hierarchy of unrestricted, context-sensitive, context-free and regular grammars and their language classes, paired with progressively restricted computational recognizers.
Context-sensitive grammar — A formal grammar whose productions rewrite a nonterminal only within declared surrounding context without decreasing string length.
Deterministic context-free grammar — A context-free grammar generating a language recognizable by a deterministic pushdown automaton.
Generalized context-free grammar — A grammar formalism extending context-free rewriting with composition functions capable of combining discontinuous or otherwise non-context-free structures.
Generalized star-height problem — The open formal-language question of whether every regular language has a generalized regular expression whose Kleene-star nesting depth is bounded by a universal constant when complement is allowed.
Kuroda normal form — A restricted production-rule form for noncontracting grammars that characterizes context-sensitive languages apart from the empty-string convention.
Matrix grammar — A controlled formal grammar whose productions must be applied in prescribed finite sequences called matrices rather than as independent rules.
Nested word — A finite or infinite linear word augmented with a properly nested matching relation between call and return positions, representing sequential order and hierarchical structure in one object.
Shortlex order — A total order on finite sequences that compares length first and lexicographic position second.
Star height problem — The formal-language problem of determining the minimum nesting depth of Kleene stars needed to express a regular language and how that depth can be decided.
Unary language — A formal language over a one-symbol alphabet, equivalently encoding a set of natural numbers by string length.