In this computational essay, I analyzed the structural behavior of context-free grammars (CFGs) using multiway systems to study derivation dynamics. I examined how different rule types affect ambiguity, growth, and derivation depth. Through a combination of formal proofs and computational experiments, I established results on rule equivalence and presence of ambiguity in limited spaces. Multiway graph visualizations were used to trace derivation paths and reveal structural patterns across rule sets.
Introduction
Introduction
This project was motivated by a structural question: What is the largest set of grammar rules that can be applied without introducing ambiguity, situations where the same final string can be reached in more than one way? In this context, a grammar is a collection of rules that describe how to rewrite a starting symbol into longer strings made of letters like “a”, “b”, or “c”. These rules are applied repeatedly, and at each step, every possible rewrite is utilized. The result is a branching structure called a multiway graph, where each node is a string and each edge represents a single rule application.
The central idea is to treat grammars not as tools for parsing language, but as systems that evolve, like a game where every move is a rewrite. Some rule sets grow quickly, others produce neat patterns, and some lead to ambiguity. To study this, I used the Wolfram Language’s built-in MultiwaySystem resource function, generating these graphs and building a set of tools to analyze their structure.
Grammar Design and Rule Taxonomy
Grammar Design and Rule Taxonomy
Defining Context Free Grammars
Defining Context Free Grammars
A context free grammar (CFG) is a formal system used to generate strings from a starting symbol, typically defined as a 4-tuple
𝐺 = (𝑉, Σ, 𝑅, 𝑆), where:
𝐺 = (𝑉, Σ, 𝑅, 𝑆), where:
◼
𝑉 is a finite set of nonterminal symbols
◼
Σ is a finite set of terminal symbols
◼
𝑅 is a set of production rules of the form 𝐴 → 𝛼 where 𝐴 ∈ 𝑉 and each character of 𝛼 is in 𝑉 ∪ Σ
◼
𝑆 ∈ 𝑉 is the start symbol
Syntactic Constraints
Syntactic Constraints
The goal is not to generate arbitrary languages, but rather to study how different types of rules affect the structure of the multiway system generated by repeated rewrites of x.
All rules utilized at the beginning of this project are of the form “x”→ rhs, where the following restrictions apply:
All rules utilized at the beginning of this project are of the form “x”→ rhs, where the following restrictions apply:
◼
“x” is used as the only non-terminal
◼
Only {“a”, “b”, “c”} may be used as terminal symbols
◼
Only the rules “x” → “axa” and “x” → “axb” may have right-hand sides of length more than 2
◼
Any right-hand side of length 2 must have exactly one “x”
Rule Types
Rule Types
We classify these rules into four distinct types based on position of x in the right-hand side:
◼
Substitution Rules
◼
Rules in which the right-hand side is made up of only terminal symbols
◼
Prefix Rules
◼
Rules that prepend a terminal symbol to “x”
◼
Postfix Rules
◼
Rules that append a terminal symbol to “x”
◼
Wrap Rules
◼
The rules “x” → “axa” and “x” → “axb”
Exploration Through Multiway Graphs
Exploration Through Multiway Graphs
To study how different rule sets behave, I used the Wolfram Language's MultiwaySystem function to generate derivation graphs. Each graph starts from the symbol "x" and applies all possible rewrites at every vertex. I have introduced tools for analyzing properties of multiway graphs.
A Simple Unambiguous System
A Simple Unambiguous System
Recall that a multiway graph of a context-free grammar is considered ambiguous if for some final string there is more than one derivation. In other words, a grammar is unambiguous if the graph is a tree.
We will begin with the basic rule set {“x”→“ax”, “x”→“b”} and visualize the multiway graph for 5 iterations as follows:
5 iterations of rule set {“x”→“ax”, “x”→“b”}
In[]:=
ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"]
Out[]=
This system contains one prefix rule and one substitution rule. The prefix rule grows the string by adding “a” to the front, while the substitution rule ends the derivation and leads to a terminal case by replacing “x” with “b”. This produces a tree-like structure, and therefore an unambiguous grammar, where each path corresponds to a string in the form b.
n
a
To verify that such a system is unambiguous, we must create a function unambiguousQ.
This function will create a list of the indegrees in an input graph, after which it will count the number of 1s in the list. It will then check if this quantity is one less than the total number of vertices in the graph.
Returns the indegree list of the graph
In[]:=
Table[VertexInDegree[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"],i],{i,VertexList[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"]]}]
Out[]=
{0,1,1,1,1,1,1,1,1,1,1}
Selects the elements in the indegree list that are equal to 1
In[]:=
Select[Table[VertexInDegree[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"],i],{i,VertexList[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"]]}],#==1&]
Out[]=
{1,1,1,1,1,1,1,1,1,1}
Returns the number of nodes in the graph that have an indegree of 1
In[]:=
Length[Select[Table[VertexInDegree[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"],i],{i,VertexList[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"]]}],#==1&]]
Out[]=
10
Notice that a graph is a tree if and only if all vertices other than the root has indegree 1.
Returns true if the number of nodes is one more than the number of nodes with indegree 1
In[]:=
Length[Select[Table[VertexInDegree[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"],i],{i,VertexList[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"]]}],#==1&]]+1==VertexCount[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",5,"StatesGraph"]]
Out[]=
True
We use this process to create a generalized function, as shown below.
Function that checks if input graph is unambiguous
In[]:=
unambiguousQ[graph_]:=Length[Select[Table[VertexInDegree[graph,i],{i,VertexList[graph]}],#==1&]]+1==VertexCount[graph]
Running unambiguousQ on the grammar defined above for 10 iterations, the result is as follows:
Checks if the rule set {“x”→“ax”, “x”→“b”} remains unambiguous after 10 iterations
unambiguousQ[ResourceFunction["MultiwaySystem"][{"x"->"ax","x"->"b"},"x",10,"StatesGraph"]]
Out[]=
True
Analyzing System Growth
Analyzing System Growth
Next, we consider a system that grows symmetrically with the rule set {“x”→“axa”, “x”→“b”}.
8 iterations of the rule set {“x”→“axa”, “x”→“b”}
In[]:=
ResourceFunction["MultiwaySystem"][{"x"->"axa","x"->"b"},"x",8,"StatesGraph"]
To analyze how quickly this system grows, the function newVertices, defined below, subtracts the number of vertices after n-1 iterations from the number of vertices after n iterations.
Function that counts the number of new vertices created by the nth iteration
Applying this on the grammar above produces the following:
Creates a list with the number of new vertices created by the 1st through 10th iterations
The result here suggests that the growth in the number of vertices is linear, which agrees with the fact that every iteration creates one non-terminal node and a terminal node.
To visualize this, the animateGrowth function defined below produces an animation showing how the multiway graph evolves over iterations. Each frame corresponds to the addition of a new iteration of rule applications, allowing for dynamic visualization. animateGrowth also utilizes the terminalHighlight function, which highlights all terminal vertices in the multiway graph by coloring them red. It provides a quick visual summary of which branches of the graph terminate and where. This is especially useful when comparing structurally similar rule sets that differ in their terminal behavior.
Function that checks if an input string is terminal given the rules of the CFG
Returns list of terminals in the graph
Function that checks for terminal nodes and highlights them in the input graph
For the graph above, terminalHighlight returns the following
Animating the terminalHighlight function results in the animateGrowth function below.
Displays a CFG after successive number of iterations in different frames
Animates the growth of the rule set {“x”→“axa”, “x”→“b”} over 10 iterations
Indeed, we see that every iteration has 2 more vertices than the iteration before.
Describing Early Ambiguous Terminal Cases
Describing Early Ambiguous Terminal Cases
In observation of ambiguous nodes, we operate on the rule set {“x”→“axb”, “x”→“ax”, “x”→“xb”}.
5 iterations of the rule set {“x”→“axb”, “x”→“ax”, “x”→“xb”}
To identify where ambiguity of a multiway graph begins, the function shortestAmbiguousVertex is implemented to find the shortest terminal string with multiple derivation paths, if one exists. This function sorts all vertices by string length and returns the first one with multiple distinct derivation paths. This helps localize ambiguity and provides concrete examples for structural analysis.
Function that returns a list with all paths from “x” to a target vertex
Returns the list of vertices in the graph in order of string length
Selects the first element in the sorted vertex list that is ambiguous
When generalizing this, it is important to observe the case in which the input graph is unambiguous to avoid a possible error from evaluation. Thus, when the input graph is unambiguous, we return “N/A”.
Function that identifies the shortest string that is represented by an ambiguous vertex in the input graph
In the example above, it is quite clear that the shortest ambiguous string is "axb," drawing an agreement to the output given by the shortestAmbiguousVertex function.
Finds the shortest string with more than one derivation in the rule set {“x”→“axb”, “x”→“ax”, “x”→“xb”}
Analyzing Derivations
Analyzing Derivations
5 iterations of {“x”→“a”, “x”→“ax”, “x”→“xb”}
After the first iteration of the system, derivation paths of the above graph are all distinct, but in the iterations following this, different sequences of rule applications begin to converge on the same terminal string.
The isolatePaths function below is a visualization tool that outputs the subgraph consisting of the paths to a target string. It implements the pathList function, defined in the previous subsection.
Returns a list of lists, each of which contains the edges of a path from “x” to “aaxb” in the graph above
We can place all edges into one, common, list and delete duplicates to create the edge list for the desired subgraph.
Function that returns the smallest subgraph with all the paths from “x” to a target vertex
Applying the isolatePaths function on the above graph to the target string “aaxb” produces the following subgraph.
Finds the smallest subgraph with all the paths from “x” to “aaxb” using the rule set {“x”→“a”, “x”→“ax”, “x”→“xb”}
Instead, to view this subgraph within the original graph, highlightPaths serves as a visualization tool that overlays all the paths that pathList would return onto the multiway graph of a given grammar. In other words, it implements isolatePaths and highlights the edges of the resulting graph in the original multiway graph.
Function that highlights all the paths from “x” to a target string
Highlights all paths from “x” to “aaxb” using the rule set {“x”→“a”, “x”→“ax”, “x”→“xb”}
Theoretical Results and Structural Claims
Theoretical Results and Structural Claims
The experiments such as those conducted above reveal several recurring structural behaviors across different rule sets. The following claims aim to characterize how rule structure influences context-free multiway systems.
Claim 1: Appending a Substitution Rule to a set of rules with no terminal nodes preserves unambiguity
Claim 1: Appending a Substitution Rule to a set of rules with no terminal nodes preserves unambiguity
Proof:
Let R be a rule set such that the respective multiway graph is unambiguous and contains no terminal nodes.
We claim that for any terminal symbol w, the extended rule set R ⋃ {“x”w} also generates an unambiguous graph.
Notice that the rule “x”w draws edges from existing vertices to terminal vertices. These terminal vertices could not have been in the original graph, indicating that the substitution rule does not draw any edges going to existing nodes, but simply adds leaves to the graph. Hence, no vertex has an indegree greater than 1 and unambiguity is preserved.
3 iterations of the rule sets {“x”“ax”, “x”“bx”} and {“x”“ax”, “x”“bx”} ⋃ {“x”“a”}
Claim 2: A rule set with both a Prefix and a Postfix Rule will have ambiguity regardless of other rules
Claim 2: A rule set with both a Prefix and a Postfix Rule will have ambiguity regardless of other rules
Proof:
Let the rule set R contain the prefix rule “#x” and the postfix rule in the rule set be “x@”.
We claim that there are two derivations of the string “#x@”.
Using the prefix rule prior to the postfix rule provides the following path: “x”“#x”“#x@”.
Using the postfix rule prior to the prefix rule provides the following path: “x”“x@”“#x@”.
Thus, the following subgraph will form independently of any other rules in the system.
Outputs a scenario of ambiguity when both a prefix and a postfix rule are used
Hence, the node “#x@” has an indegree of at least 2 and the graph is ambiguous.
Proof:
5 iterations of the rule sets {“x””a”}, {“x”“a”, “x”“bx”}, {“x”“a”, “x”“xc”}, {“x”“a”, “x”“bxc”}
Maximal Unambiguous Grammars
Maximal Unambiguous Grammars
A central motivation for this project was to explore the boundary between unambiguous and ambiguous behavior in context-free rewrite systems. Specifically, we ask: What is the largest set of rules that can be applied without introducing ambiguity? This leads to the notion of a maximal unambiguous grammar: a rule set that is unambiguous, but becomes ambiguous with the addition of any further rule.
We first define a rule set that incorporates our range of structural behaviors, as previously established:
Set of rules that are used to construct CFGs
For each nonempty subset of ruleSet, we evaluate whether the corresponding multiway graph remains unambiguous after a fixed number of iterations. From the collection of subsets that satisfy this condition, we identify the final element in the enumeration order, which represents the largest subset that produces an unambiguous multiway graph at the specified depth.
Returns the largest subset of ruleSet that is unambiguous after 5 iterations
From this result, it is clear that no set of rules larger than {“x”“a”, “x”“axa”, “x”“axb”, “x”“b”, “x”“bx”, “x”“c”, “x”“cx”} can produce an unambiguous multiway graph. However, the result above does not guarantee that this subset produces an unambiguous graph at every iteration. Hence, we proceed with the following proof.
Claim: {“x”“a”, “x”“axa”, “x”“axb”, “x”“b”, “x”“bx”, “x”“c”, “x”“cx”} remains unambiguous after every iteration
Claim: {“x”“a”, “x”“axa”, “x”“axb”, “x”“b”, “x”“bx”, “x”“c”, “x”“cx”} remains unambiguous after every iteration
Proof:
Consider an arbitrary string, either terminal or non-terminal. Let # be the first character in the string and @ be the last character in the string.
Notice that the first rule used in a path to this string must be one of the following
1
.“x” "#x"
2
.“x” "x@"
3
.“x” "#x@"
in order for the string to have this property.
Notice that in the rule set {“x”“a”, “x”“axa”, “x”“axb”, “x”“b”, “x”“bx”, “x”“c”, “x”“cx”}, no prefix rule shares its first character with a wrap rule and no postfix rule shares its last character with a wrap rule. Thus, given any string in the respective multiway graph, the first rule used in a path to this string is fixed.
Once this rule is used in the beginning of the path, if the resulting string has no non-terminal symbol, then the path has reached a terminal node, which must be the arbitrary string chosen above. Otherwise, if there is a non-terminal symbol in the resulting string, then it must be manipulated using the rules in the set into a new target string given by the originally chosen string.
However, as shown previously, the next rule used to arrive at this target string is fixed.
Thus, each edge of a path from “x” to the arbitrarily chosen string is fixed, implying that the path is unique. Hence, the resulting graph is a tree and the grammar is unambiguous for all iterations.
The following is the multiway graph of this key rule set after 3 iterations.
3 iterations of the maximal unambiguous rule set
Extensions
Extensions
The rule restrictions introduced at the beginning of this essay do not apply to the extensions considered in the following sections. Instead, any constraints on rule forms will be stated explicitly within each subsection as needed.
Generalization
Generalization
Here, we restrict our attention to rewrite rules whose right-hand sides satisfy one of the following structural conditions:
◼
The right-hand side contains exactly one terminal symbol and at most one nonterminal symbol.
◼
The right-hand side contains exactly one nonterminal symbol and exactly two terminal symbols, with one terminal appearing on each side of the nonterminal.
Unambiguity Constraint:
Unambiguity Constraint:
A set of rules produces an unambiguous multiway graph if and only if for every ordered pair of terminal symbols, (@, #), there is at most one of the following rules: x@x, xx#, x@x#
A set of rules produces an unambiguous multiway graph if and only if for every ordered pair of terminal symbols, (@, #), there is at most one of the following rules: x@x, xx#, x@x#
Proof :
We will begin with the only if direction.
Assume the rule set produces an unambiguous multiway graph. Suppose, for the sake of contradiction, that for some ordered pair (@, #), the rule set contains two or more of these three rules.
Let's consider the case where both "x"→@"x" and "x"→"x"# are present. Then we can derive:
◼
“x”→@“x”→@“x”#
◼
“x”→“x”#→@“x”#
Both derivations yield the same string @"x"#, implying that the node @"x"# has in-degree at least 2. This contradicts the assumption of unambiguity.
The same argument applies to any pair of rules among the three listed. Therefore, for each ordered pair (@,#), at most one of the three rules can be present.
We will now proceed with the if direction.
Now assume that for every ordered pair (@,#), the rule set contains at most one of the three listed rules. We want to show that the multiway graph is unambiguous.
Undecidability
Undecidability
The ambiguity problem for context-free grammars that seeks to determine whether a given CFG generates at least one string with multiple distinct derivation trees is known to be undecidable. That is, there exists no algorithm that can decide, for every CFG, whether it is ambiguous.
We will proceed with induction to show that a CFG which becomes ambiguous after k iterations exists for all k≥2.
As a base case, we will first prove for k=2.
We see this from the rule set {“x”→“ax”, “x”→“xb”} as shown in Claim 2 of Theoretical Results and Structural Claims.
Now, suppose we are given a CFG that becomes ambiguous after n derivation steps. By introducing a new nonterminal symbol that is directed to the original root of the graph, a CFG can be constructed that becomes ambiguous after n+1 derivation steps.
Since there is no upper bound on the number of iterations required before ambiguity appears, any algorithm that attempts to detect ambiguity by finite unfolding of derivation steps must fail in general. This unbounded deferral of ambiguity implies that no finite procedure can decide ambiguity for all CFGs. The problem is therefore undecidable.
This result aligns with the classic result in formal language theory that the ambiguity problem for CFGs is not recursively enumerable.
Generating Functions
Generating Functions
One unique and fascinating extension of context-free grammars involves the use of generating functions to analyze the growth behavior. That is, generating function may represent the number of strings in a language with any given length.
Function that returns a list with the number of strings at each length for an input graph
We proceed to construct CFGs using generating functions in the following examples.
Example 1: {1,1,1,1,...}
Example 1: {1,1,1,1,...}
Hence,
Thus, the resulting graph is as follows:
Graph of CFG with the desired generating function
This result is supported by the following evaluation:
Number of strings with each length in the above graph
Example 2: {1,2,3,4,...}
Example 2: {1,2,3,4,...}
However, in order to find a closed form of this infinite arithmetico-geometric series, the following manipulation is necessary:
The resulting graph is as follows:
Graph of CFG with the desired generating function
This result is supported by the following evaluation:
Number of strings with each length in the above graph
Example 3: Fibonacci Sequence
Example 3: Fibonacci Sequence
As described in example 1, the x term on the right hand side represents the starting node of the CFG rather than a part of the rule set.
Thus, the resulting graph is as follows:
Graph of CFG with the desired generating function
This result is supported by the following evaluation:
Number of strings with each length in the above graph
Conclusions
Conclusions
This paper investigated the structural behavior of context-free grammars through the framework of multiway systems, with a focus on ambiguity, derivation depth, and the effects of rule types. By classifying these rules and analyzing their interactions, I established formal results on unambiguity conditions and the structural consequences of combining prefix, postfix, and wrap rules. These results were supported by rigorous proofs and computational experiments, with multiway graph visualizations used to trace derivation paths and clarify the emergence of ambiguity. To support this analysis, I developed a suite of functions for detecting ambiguity, tracking growth, and visualizing derivation structures, which enabled systematic exploration of a wide range of grammars. Together, these findings contribute to a deeper understanding of how local rule design governs global grammatical behavior in context-free grammars.
Further Directions
Further Directions
◼
Quantitative Analysis of Ambiguity Growth: Develop formal metrics to measure how ambiguity evolves across derivation depth, such as the rate of ambiguous node emergence or the distribution of in-degrees in the multiway graph
◼
Decidability Thresholds for Rule Length: Identify the minimum rule length under which the ambiguity problem becomes decidable for grammars with a single nonterminal
◼
Trend Analysis of Ambiguity: Plot the percentage of ambiguous nodes as a function of derivation depth to identify structural trends, thresholds, or phase transitions in ambiguity behavior
◼
Construction of Delayed Ambiguity Examples: Search for grammars that appear unambiguous for many iterations but eventually become ambiguous, in order to better understand the boundary between decidable and undecidable ambiguity detection
References
References
◼
Wolfram, S. (2002). A New Kind of Science. https://www.wolframscience.com/nks/notes-5-6--formal-languages-and-multiway-systems/
◼
Context Free Grammars And Generating Functions. (2018, January 27). Gopinath a R. https://g-ar.github.io/posts/context-free-grammars-and-generating-functions/
Acknowledgements
Acknowledgements
I would like to thank my incredible mentor Henry Gustafson for his guidance and mathematical insight throughout this project. His feedback on both the theoretical and computational aspects of my work was invaluable. I also express appreciation to my advocate Adam Millar for insightful discussions on graph theory structures that influenced several conceptual directions in my work. I’d like to thank the program directors Rory Foulger, Eryn Gillam, and Megan Davis, as well as faculty and staff for creating such a supportive and intellectually rich environment. Special thanks to my fellow students for the many thought-provoking conversations and occasional distractions that made the experience all the more enjoyable. Finally, I’d like to show my gratitude to Dr. Stephen Wolfram for introducing me to context-free grammars and proposing this project to me.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Unambiguity properties in context-free grammars: identifying a maximal unambiguous rule set
by Girish Prasad
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3499683
by Girish Prasad
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3499683