Formal Grammars & String Rewriting

← Back to Domain-Specific Families

Abstractions about generating and constraining formal languages, covering grammar hierarchies and classes (Chomsky hierarchy, context-sensitive grammar, matrix grammar), string-rewriting and automaton systems (L-systems, Markov algorithms, nested stack automata), and structural word or pattern properties (shortlex order, star height problem, ABACABA pattern).

21 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• ABACABA pattern — A recursively generated word obtained by placing a new central symbol between two copies of the preceding word, producing lengths one less than powers of two.
• 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.
• Digital Data — Represent data as sequences over a finite discrete alphabet, interpreting physical states through symbol thresholds and shared codes so content can be stored, transmitted, copied, computed, and error-checked independently of one carrier.
• ECLR-attributed grammar — An LR-attributed grammar class that groups inherited attributes into equivalence classes so a one-pass compiler generator can reuse evaluation structure and reduce attribute-handling overhead.
• Free monoid — The monoid of all finite words over an alphabet under concatenation with the empty word as identity, characterized by unique extension of every generator map to a monoid homomorphism.
• Generalized context-free grammar — A grammar formalism extending context-free rewriting with composition functions capable of combining discontinuous or otherwise non-context-free structures.
• Gestalt pattern matching — A recursive string-similarity algorithm that anchors on a longest common substring and repeats on the unmatched left and right regions.
• Kuroda normal form — A restricted production-rule form for noncontracting grammars that characterizes context-sensitive languages apart from the empty-string convention.
• L-system — A parallel formal rewriting system that repeatedly replaces every symbol according to production rules, often interpreting resulting strings as branching geometry.
• Markov algorithm — A deterministic ordered string-rewriting procedure that repeatedly applies the first applicable production, halting when no rule applies or a designated terminal rule fires.
• Matrix grammar — A controlled formal grammar whose productions must be applied in prescribed finite sequences called matrices rather than as independent rules.
• Nested stack automaton — A finite-state automaton with a recursively nested stack store whose head operates on the innermost active stack.
• 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.
• Path ordering (term rewriting) — A well-founded term ordering based on root-symbol precedence and recursive comparison of subterms.
• S-attributed grammar — An attribute grammar using only synthesized attributes, so each parse-tree node's attributes depend solely on its children and can be evaluated naturally during bottom-up parsing.
• Separating words problem — The automata problem of finding the smallest deterministic finite automaton that accepts one of two given words and rejects the other.
• 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.