Grammar is defined as the whole system and structure of a language or of languages in general, usually taken as consisting of syntax and morphology, phonology and semantics. It is a universal feature of every language. A multiway system is a substitution system in which multiple states are permitted at any stage. In this computational essay, we will utilise substitution rules, multiway systems, graphs to discover the computational aspects of grammar.
Introduction
Introduction
A multiway system can be described as taking each of its states and repeatedly replacing it according to some rule or rules with a collection of states, merging any states produced that are identical. Grammar is a part of every language known to man and thus we can apply the substitution rules in primitive and complex grammars and visualise them using multiway systems. The basic knowledge required for following this paper is a basic understanding of Non-Deterministic Finite Automatons and Theory of Computation.
Grammars and their visualisations using multiway systems
Grammars and their visualisations using multiway systems
A brief overview of multiway systems
A brief overview of multiway systems
Multiway systems are usually used for string substitution systems. Similar to substitution systems, we can construct multiway systems for our grammar models in which we include a separate path for every possible updating event that can occur. We can use different parameters and functionalities in the Wolfram Language and make connections between the structure of the graph and the actual grammars.
In[]:=
ResourceFunction["GraphRemoveLooseEnds"][ResourceFunction["NestGraphTagged"][n{3n,2n,n+1},{0},11],All]
Out[]=
An example of a Resource Function for a Multiway System
Use Multiway-Systems to compute grammars:
In[]:=
ResourceFunction["MultiwaySystem"][{"S"->"","S"->"B","S"->"AAB","B"->"ASB"},"S",2,"StatesGraph"]
Out[]=
Increase in number of iterations leads to more complicated graphs for most grammars
Manipulate[ResourceFunction["MultiwaySystem"][{"S"->"","S"->"B","S"->"AAB","B"->"ASB"},"S",n,"StatesGraph"],{n,1,8,1}]
Out[]=
Look at the exponential change graphs exhibit using EdgeCount
Out[]=
Look at the exponential change graphs exhibit using VertexCount
Out[]=
Using different parameters of the MultiwaySystem Resource Function, we can gauge the general structure at a particular step, and how it corresponds to the properties of the multiway system.
Look at the general structure of MultiwaySystems using different parameters
Show the structure of the graph,without labels:
Implementing Causal and Evolution Graph Instances for Multiway Systems
Implementing Causal and Evolution Graph Instances for Multiway Systems
Generate causal graphs for all possible choices of event sequences:
We can look at the number of connected components created by the CausalGraphInstances of the multiway system to see how many disparate states are there compared to connected graphs.
Finding the number of "weakly" connected components
This indicates that for step 3, the number of "weakly" connected components and the number of disparate unconnected components are equal, we can test this hypothesis for different number of iterations as well.
The hypothesis is proven incorrect when considering the case of n = 4.
Context-Free Grammars
Context-Free Grammars
Context-Free Grammars is a formal grammar which is used to generate all possible strings in a given formal language. Any given Context-Free
Grammar (CFG) G can be defined as a set of 4 tuples where
G= (V, T, P, S).
T describes a finite set of terminal symbols.
V describes a finite set of non-terminal symbols
P describes a set of production rules
S is the start symbol.
We can model CFGs using multiway systems in an efficient manner. The following example generates strings of the form 010101...
Grammar (CFG) G can be defined as a set of 4 tuples where
G= (V, T, P, S).
T describes a finite set of terminal symbols.
V describes a finite set of non-terminal symbols
P describes a set of production rules
S is the start symbol.
We can model CFGs using multiway systems in an efficient manner. The following example generates strings of the form 010101...
This type of CFG only generates a tree-structure- we can verify this by using the TreeGraphQ function.
The Evolution Events Graph Structure for a "palindrome" language, which is generated by the following rules also creates Tree-like structures which have a beautiful symmetry to them
This indicates that there is no ambiguity in these formal languages. We can now take a look at ambiguous context free grammars that provide a very interesting EvolutionEventsGraphStructure
Context Sensitive Grammars
Context Sensitive Grammars
A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols.
Generate a table of the first ten multiway systems for a CSG
Check TreeGraphQ for the first ten iterations of the CSG
Look at the EvolutionEventsGraphStructure for the first ten iterations of the CSG
Only trivial cases in most Context-Sensitive Grammars create Tree Graphs, the rest do not due to ambiguities present in the language.
Create a rule for a CSG
Generate a table of the first ten multiway systems for the CSG
Create Evolution and Causal Graph Instances for the CSG Rules for the first ten iterations.
We can overlay the CausalGraphStructures on top of the EvolutionEventsGraphStructure to get an idea of how much they intersect!
Use Manipulate to overlay them for different iterations of the CSG multiway system
Use Manipulate to show them side by side for different iterations of the CSG multiway system
We look at Branchial graphs for Context-Sensitive Grammars due to their interesting properties. Branchial graph instances for context-sensitive grammars are interesting because they provide a visual representation of the syntactic structures generated by these grammars. Context-sensitive grammars are more powerful than regular grammars and context-free grammars, allowing for more complex and nuanced language patterns.
Regular Languages
Regular Languages
The left-hand side of each rule must consist of one non-terminal symbol, and the right-hand side can contain only one non-terminal symbol.
Regular languages can always be parsed by Finite-State Automaton and always generate tree-structures. The Myhill–Nerode theorem ensures that a unique minimal DFA can always be found, but doing this in general is PSPACE Complete. The upper bound for the number of distinct finite automaton is given by the OEIS Sequence A181554
Creating Context-Free Grammar for a Conlang- Toki Pona
Creating Context-Free Grammar for a Conlang- Toki Pona
Introduction to Toki Pona
Introduction to Toki Pona
Toki Pona is a philosophical artistic constructed language known for its small vocabulary, simplicity, and ease of acquisition. It was created by Sonja Lang, a Canadian linguist and translator, to simplify thoughts and communication. It is based on the Sapir Whorf Hypothesis and has a finite-language. We can create a CFG for Toki-Pona, with the caveat that we use Regex to denote names.
Plotting Multiway-Systems for Toki-Pona CFG
Plotting Multiway-Systems for Toki-Pona CFG
We can plot various functionalities for multiway systems for the TokiPonaCFG.
Compared to the different grammars we saw before this, the TokiPonaCFG CausalGraphStructure has disconnected-highly connected components,i.e, components which are not connected to each other but are highly connected by themselves. Disconnected-highly connected components suggest that certain linguistic elements or rules within the grammar do not interact or affect each other. This might lead to interesting implications for language comprehension, generation, or analysis. In this case, disconnected components represent independent grammatical features or syntactic structures that exist in isolation, which allowing for more flexibility, creativity, or ambiguity in language use. Creating CFGs for more expressive languages will lead to more disconnected-highly connected components.
Also compared to the previous grammars, the BranchialGraphStructures for Toki-Pona contain less-disparate complete graphs.
Given a list of strings in English, Determine a Context-Free Grammar for it
Given a list of strings in English, Determine a Context-Free Grammar for it
In this part of the paper, we will discuss generating a CFG for given strings in the English language using TextStructure and POS Tagging.
We notice that after a set number of iterations, the multiway system "exhausts" the possibilities of the sentence and starts reiterating.
This function calculates the number of iterations that are required by a context-free grammar to generate a string.
Plot the number of IterationsUsed for the Nth sentence
We can look at the Histogram structure for this and then we can look at it's comparison with Zipf's law
A brief description of Zipf's Law
Can we use this functionality to check the similarity of sentences?
The structure of two sentences can be compared by computing and processing their respective constituent graphs.
Display the constituent tree of a sentence as a graph.
Compute the matrix of distances between all the vertices of this graph .
Proceed similarly for another sentence.
Compare the structure of the two sentences by comparing their distance matrices.
This implies that the two sentences have the same structure, so now let's look at the CFG similarity
Therefore, the IterationsUsed for the sentence "Time flies like an arrow" is 5 - which is the same, thus the IterationsUsed function matches the similarity structure for these particular set of sentences. The logical next step is to try and generalize this for a long set of sentences using different metrics to see which one fits the IterationsUsed metric the most
1. EditDistance
1. EditDistance
The Levenshtein edit distance is a string metric, i.e. a way of quantifying how dissimilar two strings (e.g., words) are to one another, that is measured by counting the minimum number of operations required to transform one string into the other. It allows allows deletion, insertion and substitution. We apply it to the EdgeRules of the ConstituentGraphs formed by the TextStructures of Sentences.
We load some data using the inbuilt WikipediaData functionality, plot the EditDistance for consecutive sentences and compare them to the IterationsUsed for consecutive sentences.
Load Data using WikipediaData
Define a function that finds the EditDistance between the grammar rules of two strings
Plot the EditDistanceData
Find the IterationsUsedData - use absolute value
Plot the EditDistanceData and IterationsUsedData on the same graph
The absolute difference between the IterationsUsedData and EditDistanceData
As we can see, the difference between the IterationsUsedData and EditDistanceData for dissimilar sentences is of a large magnitude. We can possibly hypothesize that the difference between the magnitude of EditDistanceData and IterationsUsedData for similar sentences will be lower.
Get IterationsUsed Data for Similar Sentences
Get EditDistance Data for Similar Sentences
Plot them on a graph
Plot the absolute difference on a plot
As we can see, the magnitude of difference for the EditDistanceSimilarSentencesData and IterationsUsedSimilarSentencesData is very small, barely reaching a magnitude of 5. This indicates that the IterationsUsed functionality is comparable to EditDistance for similar sentences.
2. Needleman Wunsch Similarity
2. Needleman Wunsch Similarity
The Needleman-Wunsch algorithm finds the optimal alignment of two strings (the source string (s) and the target string (t)). It is also referred as optimal matching algorithm and the global alignment technique. We apply it to the EdgeRules of the ConstituentGraphs formed by the TextStructures of Sentences.
Create NW-Finder
Find the absolute difference between two consecutive sentences using NeedlemanWunsch
Find the absolute difference between two consecutive sentences using IterationsUsed
Plot the data on a graph
Plot the absolute difference
Similar to EditDistance, the magnitude of difference between IterationsUsed and NeedlemanWunsch reaches high magnitudes for dis-similar sentences. We can now test it for similar-sentences.
NeedlemanWunsch for Similar Sentences
Plot NeedlemanWunsch for Similar Sentences and EditDistances for Similar Sentences on a graph
Plot the absolute difference
3. SmithWaterman Similarity
3. SmithWaterman Similarity
The Smith–Waterman algorithm performs local sequence alignment for determining similar regions between two strings of nucleic acid sequences or protein sequences. Instead of looking at the entire sequence, the Smith–Waterman algorithm compares segments of all possible lengths and optimizes the similarity measure, using essentially what is a "greedy algorithm" to compare strings of nucleic acids. We can use it for our sentences.
Create SmithWaterman similarity finder for two sentences
Find the absolute value of the SmithWatermanData
Plot the SmithWatermanData and IterationsUsed Data for dis-similar sentences
In stark contrast to the Levenshtein Edit Distance and the Needleman Wunsch Distance, the SmithWaterman distance is much similar to the IterationsUsedData and the magnitude of difference isn't very large.
Plotting the absolute value of difference between IterationsUsed and SmithWaterman
Surprisingly, the SmithWatermanSimilarSentencesData performs poorly relative to it's previous performance for similar sentences
Creating a Finite State Automaton
Creating a Finite State Automaton
Finite automata (FA), also widely known as finite state automata (FSA), are a mathematical model of computation based on the ideas of a system changing state due to inputs supplied to it and the transitions from state to state being governed by a fixed set of rules. An FSA can be defined as a 5-tuple - FSA = { Q, Σ, q, F, δ } where
Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.
Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.
Create Closure-DeltaHat and IsValid functions, code provided by Tomas De Camino Beck, Cenfotec University, Costa Rica
We can also create a Pushdown automaton for Context-Free Grammars using the inbuilt functionality of Stacks
Check if Stack is Empty
Push element onto Stack
Verify that the stack is not empty
Look at the Length of the Stack
Peek the latest element
Remove the latest element
Check the length
Visualize the stack after pushing 1000 elements to it
Let’s look at the context-free grammar for a language
Create a stack
Function to accept the CFG string
Question: What's the optimal "move" you can make to increase the number of vertices ?
Question: What's the optimal "move" you can make to increase the number of vertices ?
The optimal move can be defined as a singular change to the end state of a rule in a multiway system that leads to the maximal change in the number of vertices
Number of vertices at the 8th iteration
Plot the 8th iteration after a "move"
The number of vertices after a move
Number of Vertices for a complex MultiwaySystem
Number of Vertices after a "pessimal" move
It is clear to see why mapping "S" -> "S" is a pessimal move because a multiway system decreases the number of vertices for a isomorphic rule. We shall now try and implement it for a relatively simple substitution system using a brute-force algorithm and a heuristic solution.
Generate rules
Generate OptimalMoveFinder function
Create an overloaded function!
Create a flattened list of tuples - generating every possible combination - including duplicates
Building a Brute-Force Algorithm
Thus, {"", "abSa", "bSSb"} and {"","aSab","bSSb"} are the two optimal moves, indicating that putting "S" in between of long strings may be the optimal solution.
Conclusion and Further Work
Conclusion and Further Work
In this paper, we explored context-free and context-sensitive grammars through a computational lens using Multiway Systems. We plotted the first multiway system for a con-lang, discovered new functionalities with respect to the number of iterations required by a context-free grammar to exhaust a sentence, visualized context-free grammars using Pushdown Automatons and explored a heuristic solution for a novel problem. Future work will include exploring the optimal move problem more and creating a Sequitur algorithm for implementing context-free grammars for discrete symbols.
Bibliography
Bibliography
1. "Multicomputation with Numbers: The Case of Simple Multiway Systems—Wolfram Institute Bulletins. 7 Oct. 2021, https://www.wolframinstitute.org/bulletins/2021/10/multicomputation-with-numbers-the-case-of-simple-multiway-systems/."
2. "Compare the Structure of Sentences: New in Wolfram Language 11. https://www.wolfram.com/language/11/text-and-language-processing/compare-the-structure-of-sentences.html?product=mathematica. Accessed 13 July 2023."
2. "Compare the Structure of Sentences: New in Wolfram Language 11. https://www.wolfram.com/language/11/text-and-language-processing/compare-the-structure-of-sentences.html?product=mathematica. Accessed 13 July 2023."
4. "Note (b) for The Notion of Attractors: A New Kind of Science | Online by Stephen Wolfram [Page 957]. https://www.wolframscience.com/nks/notes-6-7--finite-automata/. Accessed 13 July 2023."
5. "JohnH_312. "Context-Free Grammar." R/Tokipona, 7 June 2022, www.reddit.com/r/tokipona/comments/v70v9o/contextfree_grammar/."
6. "Ambiguous Grammar." Wikipedia, 23 Feb. 2023. Wikipedia, https://en.wikipedia.org/w/index.php?title=Ambiguous_grammar&oldid=1141097147."
7. "Examples for Working with Finite State Automata - Online Technical Discussion Groups—Wolfram Community. https://community.wolfram.com/groups/-/m/t/2355569. Accessed 13 July 2023."
8."Chomsky Hierarchy." Wikipedia, 13 July 2023. Wikipedia, https://en.wikipedia.org/w/index.php?title=Chomsky_hierarchy&oldid=1165217771"
9."Construct Pushdown Automata for given Languages." GeeksforGeeks, 4 Apr. 2018, https://www.geeksforgeeks.org/construct-pushdown-automata-given-languages/."
5. "JohnH_312. "Context-Free Grammar." R/Tokipona, 7 June 2022, www.reddit.com/r/tokipona/comments/v70v9o/contextfree_grammar/."
6. "Ambiguous Grammar." Wikipedia, 23 Feb. 2023. Wikipedia, https://en.wikipedia.org/w/index.php?title=Ambiguous_grammar&oldid=1141097147."
7. "Examples for Working with Finite State Automata - Online Technical Discussion Groups—Wolfram Community. https://community.wolfram.com/groups/-/m/t/2355569. Accessed 13 July 2023."
8."Chomsky Hierarchy." Wikipedia, 13 July 2023. Wikipedia, https://en.wikipedia.org/w/index.php?title=Chomsky_hierarchy&oldid=1165217771"
9."Construct Pushdown Automata for given Languages." GeeksforGeeks, 4 Apr. 2018, https://www.geeksforgeeks.org/construct-pushdown-automata-given-languages/."
Acknowledgements
Acknowledgements
Firstly, I'd like to thank my parents and family for allowing me to attend this summer program and supporting me when I was homesick! I'd like to thank Akansha Gupta for helping me out with the ideation of the project. I'd also like to thank Dr. Stephen Wolfram for his inspirational talks and my mentor Carolyn Applebaum for helping me throughout the project. Thank you to Jonathan Gorard for helping me with the brute-force algorithm in the optimal solution problem. I'd like to thank the TAs and directors - especially Henry, Nora, William, Nicolo. Last but not least, I'd like to thank Dr. Rajesh Bhatt for helping me develop an interest in computational syntax and for answering my sometimes-annoying questions!
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Exploring computational dynamics of formal-language syntax using multiway systems
by Navvye Anand
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2965584
by Navvye Anand
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2965584