Implementing formal power series
Hi @alsultanm and @mhd91,
I thought of an efficient way to implement formal power series. It exploits the Python library re
(see here), which allows to define and manipulate regular languages (also called regular expressions). The library can do a lot of stuff, most of which is useless for our purposes. However, it is smart enough to understand something like "(a+b)*(c+d)"
as what I would write mathematically as \{s\in\{a,b,c,d\}^*\mid s = s_1 s_2,\ \text{such that } s_1\in\{a,b\}^*\ \text{and }s_2\in\{c,d\}\}
(here \{a,b\}^*
is the set of strings formed by concatenating letters a
and b
in any way).
For instance, check the following Python code (written by ChatGPT):
import re
class RegularExpression:
def __init__(self, regex):
self.regex = regex
def match(self, input_string):
# checks if "input_string" belongs to the regular expression "self"
pattern = "^" + self._convert_to_regex(self.regex) + "$"
return bool(re.match(pattern, input_string))
def _convert_to_regex(self, regex):
# don't be scared by this function, it's just to convert some notation
# in particular, in package "re" what we call addition is indicated by symbol "|"
regex = regex.replace('+', '|')
return regex
# Example usage:
regex = "(a+b)*(c+d)"
re_obj = RegularExpression(regex)
print(re_obj.match("ac")) # Output: True
print(re_obj.match("ad")) # Output: True
print(re_obj.match("bc")) # Output: True
print(re_obj.match("c")) # Output: True
print(re_obj.match("bd")) # Output: True
print(re_obj.match("a")) # Output: True
print(re_obj.match("ab")) # Output: False
print(re_obj.match("aaabbbac")) # Output: True
You should be able to run this script on your computer. It takes the regular expression (a+b)*(c+d)
and another string, like ac
, and checks if ac
belongs to the language corresponding to (a+b)*(c+d)
. We can use this script as starting point for our class Series
.
The main thing to change is that in series we do not only have strings but also numbers associated to each string. Moreover, operations of addition +
and multiplication
(concatenation) need to be re-defined such that, for example 2a+3a
is equal to 3a
and 2a3b
is equal to 5ab
.