commit 1d15f74b0ec8492ed44f154e3d376bd6fbeda9d3
parent f42898f84f04c1b41e0e37e2f2f5c5649a7b58b4
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 18 Sep 2025 20:00:38 +0200
commit with codex
Diffstat:
7 files changed, 26 insertions(+), 0 deletions(-)
diff --git a/2_ambiguous_cfg b/2_ambiguous_cfg
@@ -2,6 +2,9 @@
A *2-ambiguous CFG* is an [ambiguous_CFG] where every [word] has at most two [parse_trees]
+- [universality_2_ambiguous_CFG]
+- [equivalence_2_ambiguous_CFG]
+
Up: [degree_of_ambiguity_cfg]
Aliases: 2 ambiguous CFGs, 2ambiguous CFG, 2ambiguous CFGs
diff --git a/context_free_grammar b/context_free_grammar
@@ -35,9 +35,11 @@
## Problems
- [context_free_grammar_equivalence]
+- [context_free_grammar_inclusion]
- [context_free_grammar_universality]
- [smallest_grammar_problem]
- [context_free_grammar_membership]
+- [context_free_grammar_ambiguity_problem]
## Fields
@@ -46,6 +48,7 @@
## Extensions
- [probabilistic_grammar]
+- [conjunctive_grammar]
- [multiple_context_free_grammar]
## Results
diff --git a/context_free_grammar_ambiguity_problem b/context_free_grammar_ambiguity_problem
@@ -0,0 +1,9 @@
+# Context free grammar ambiguity problem
+
+The [computational_problem] of [deciding] if a [CFG] is [uCFG]
+
+Already [undecidable] for very restricted [linear_CFGs] by reduction from [PCP]
+
+Up: [ambiguity_problem], [context_free_grammar]
+
+See also: [context_free_language_inherent_ambiguity_problem]
diff --git a/context_free_grammar_equivalence b/context_free_grammar_equivalence
@@ -7,3 +7,5 @@ Two [CFGs] are *equivalent* if they recognize the same [formal_language]
Up: [context_free_grammar], [language_equivalence]
Aliases: CFG equivalence, CFG equivalent, equivalent CFG, grammar equivalent
+
+See also: [context_free_grammar_inclusion]
diff --git a/context_free_grammar_inclusion b/context_free_grammar_inclusion
@@ -0,0 +1,7 @@
+# Context free grammar inclusion
+
+It is [undecidable], already for [uCFLs], and already for [linear_uCFLs], see [asveld2000note]
+
+Up: [inclusion_problem], [context_free_grammar]
+
+Aliases: CFG inclusion
diff --git a/context_free_grammar_unambiguous b/context_free_grammar_unambiguous
@@ -10,6 +10,7 @@ There are some [CFLs] admitting no uCFG (namely, those that are not [uCFLs]), an
[Computational_problems]:
- [unambiguous_cfg_equivalence_problem]
+- [unambiguous_cfg_inclusion_problem]
- [unambiguous_cfg_universality]
Up: [unambiguity], [context_free_grammar]
diff --git a/language_inclusion b/language_inclusion
@@ -4,5 +4,6 @@
- [language_inclusion_bounded]
- [DPDA_language_inclusion]
- [automaton_inclusion]
+- [CFG_language_inclusion]
Up: [formal_language_computational_problems], [set_inclusion]
