Brzozowski algebraic method
Brzozowski algebraic method is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Description
The Brzozowski Algebraic Method is a technique used in automata theory, specifically for constructing the minimal deterministic finite automaton (DFA) from a given nondeterministic finite automaton (NFA). It was introduced by Janusz Brzozowski in 1962 and involves the use of algebraic transformations to simplify and optimize automata.
As the workings of the algorithm are clearly described in the linked article they will not be repeated here.
- Task
Implement the Brzozowski Algebraic Method to convert an NFA representation into a regular expression. The implementation should:
1. Take as input:
- A 2D array 'a' representing the transition matrix of the NFA - An array 'b' representing the final states
2. Include functionality to:
- Handle basic regular expression operations (Empty, Epsilon, Character, Union, Concatenation, Star) - Print regular expressions in a readable format - Simplify regular expressions using algebraic rules
3. Apply the Brzozowski algorithm to:
- Process the transition matrix in reverse order - Update transitions using Star and Concatenation operations - Combine paths using Union operations - Generate a final regular expression representing the language accepted by the NFA
4. Include simplification rules for:
- Eliminating redundant unions (e + e → e) - Handling identity elements (e·1 → e, 1·e → e) - Handling zero elements (e·0 → 0, 0·e → 0) - Simplifying star operations (0* → 1, 1* → 1)
The implementation should be able to process the given example input and produce both the raw and simplified regular expressions as output.
C#
using System;
abstract class RE
{
public static readonly RE empty = new Empty();
public static readonly RE epsilon = new Epsilon();
public abstract override string ToString();
public abstract override bool Equals(object obj);
public abstract override int GetHashCode();
}
class Empty : RE
{
public override string ToString() => "0";
public override bool Equals(object obj) => obj is Empty;
public override int GetHashCode() => typeof(Empty).GetHashCode();
}
class Epsilon : RE
{
public override string ToString() => "1";
public override bool Equals(object obj) => obj is Epsilon;
public override int GetHashCode() => typeof(Epsilon).GetHashCode();
}
class Car : RE
{
public string c;
public Car(string c) => this.c = c;
public override string ToString() => c;
public override bool Equals(object obj) => obj is Car other && c == other.c;
public override int GetHashCode() => c.GetHashCode();
}
class Union : RE
{
public RE e, f;
public Union(RE e, RE f)
{
this.e = e;
this.f = f;
}
public override string ToString() => $"{e}+{f}";
public override bool Equals(object obj) => obj is Union other && e.Equals(other.e) && f.Equals(other.f);
public override int GetHashCode() => e.GetHashCode() * 17 + f.GetHashCode();
}
class Concat : RE
{
public RE e, f;
public Concat(RE e, RE f)
{
this.e = e;
this.f = f;
}
public override string ToString() => $"({e})({f})";
public override bool Equals(object obj) => obj is Concat other && e.Equals(other.e) && f.Equals(other.f);
public override int GetHashCode() => e.GetHashCode() * 17 + f.GetHashCode();
}
class Star : RE
{
public RE e;
public Star(RE e) => this.e = e;
public override string ToString() => $"({e})*";
public override bool Equals(object obj) => obj is Star other && e.Equals(other.e);
public override int GetHashCode() => e.GetHashCode() * 31;
}
class Program
{
static RE SimpleRe(RE e)
{
RE Simple(RE expr)
{
if (expr is Union union)
{
RE e_e = Simple(union.e);
RE e_f = Simple(union.f);
if (e_e.Equals(e_f))
return e_e;
else if (e_e is Union e_e_union)
return Simple(new Union(e_e_union.e, new Union(e_e_union.f, e_f)));
else if (e_e.Equals(RE.empty))
return e_f;
else if (e_f.Equals(RE.empty))
return e_e;
else
return new Union(e_e, e_f);
}
else if (expr is Concat concat)
{
RE e_e = Simple(concat.e);
RE e_f = Simple(concat.f);
if (e_e.Equals(RE.epsilon))
return e_f;
else if (e_f.Equals(RE.epsilon))
return e_e;
else if (e_e.Equals(RE.empty) || e_f.Equals(RE.empty))
return RE.empty;
else if (e_e is Concat e_e_concat)
return Simple(new Concat(e_e_concat.e, new Concat(e_e_concat.f, e_f)));
else
return new Concat(e_e, e_f);
}
else if (expr is Star star)
{
RE e_e = Simple(star.e);
if (e_e is Empty || e_e is Epsilon)
return RE.epsilon;
else
return new Star(e_e);
}
else
return expr;
}
RE prev_e = null;
while (!e.Equals(prev_e))
{
prev_e = e;
e = Simple(e);
}
return e;
}
static RE Brzozowski(RE[][] a, RE[] b)
{
int m = a.Length;
for (int n = m - 1; n >= 0; n--)
{
RE a_nn = a[n][n];
b[n] = new Concat(new Star(a_nn), b[n]);
for (int j = 0; j < n; j++)
a[n][j] = new Concat(new Star(a_nn), a[n][j]);
for (int i = 0; i < n; i++)
{
b[i] = new Union(b[i], new Concat(a[i][n], b[n]));
for (int j = 0; j < n; j++)
a[i][j] = new Union(a[i][j], new Concat(a[i][n], a[n][j]));
}
for (int i = 0; i < n; i++)
a[i][n] = RE.empty;
}
return b[0];
}
static void Main(string[] args)
{
RE[][] a = new RE[][]
{
new RE[] { RE.empty, new Car("a"), new Car("b") },
new RE[] { new Car("b"), RE.empty, new Car("a") },
new RE[] { new Car("a"), new Car("b"), RE.empty },
};
RE[] b = new RE[] { RE.epsilon, RE.empty, RE.empty };
RE re = Brzozowski(a, b);
Console.WriteLine(re.ToString());
Console.WriteLine();
Console.WriteLine(SimpleRe(re).ToString());
}
}
C++
#include <iostream>
#include <string>
#include <vector>
#include <memory>
class RegularExpression {
public:
virtual ~RegularExpression() {}
virtual std::shared_ptr<RegularExpression> simplify() = 0;
virtual std::string sprintRE() = 0;
virtual bool equals(std::shared_ptr<RegularExpression> other) = 0;
};
class EmptyExpr : public RegularExpression {
public:
std::shared_ptr<RegularExpression> simplify() override {
return std::make_shared<EmptyExpr>();
}
std::string sprintRE() override {
return "0";
}
bool equals(std::shared_ptr<RegularExpression> other) override {
return dynamic_cast<EmptyExpr*>(other.get()) != nullptr;
}
};
class EpsilonExpr : public RegularExpression {
public:
std::shared_ptr<RegularExpression> simplify() override {
return std::make_shared<EpsilonExpr>();
}
std::string sprintRE() override {
return "1";
}
bool equals(std::shared_ptr<RegularExpression> other) override {
return dynamic_cast<EpsilonExpr*>(other.get()) != nullptr;
}
};
class CarExpr : public RegularExpression {
public:
char c;
CarExpr(char c) : c(c) {}
std::shared_ptr<RegularExpression> simplify() override {
return std::make_shared<CarExpr>(c);
}
std::string sprintRE() override {
return std::string(1, c);
}
bool equals(std::shared_ptr<RegularExpression> other) override {
CarExpr* o = dynamic_cast<CarExpr*>(other.get());
return o != nullptr && c == o->c;
}
};
class UnionExpr : public RegularExpression {
public:
std::shared_ptr<RegularExpression> e, f;
UnionExpr(std::shared_ptr<RegularExpression> e, std::shared_ptr<RegularExpression> f) : e(e), f(f) {}
std::shared_ptr<RegularExpression> simplify() override;
std::string sprintRE() override {
return e->sprintRE() + "+" + f->sprintRE();
}
bool equals(std::shared_ptr<RegularExpression> other) override {
UnionExpr* o = dynamic_cast<UnionExpr*>(other.get());
if (o != nullptr) {
// Since Union is commutative, check both orders
return (e->equals(o->e) && f->equals(o->f)) || (e->equals(o->f) && f->equals(o->e));
}
return false;
}
};
class ConcatExpr : public RegularExpression {
public:
std::shared_ptr<RegularExpression> e, f;
ConcatExpr(std::shared_ptr<RegularExpression> e, std::shared_ptr<RegularExpression> f) : e(e), f(f) {}
std::shared_ptr<RegularExpression> simplify() override;
std::string sprintRE() override {
return "(" + e->sprintRE() + ")(" + f->sprintRE() + ")";
}
bool equals(std::shared_ptr<RegularExpression> other) override {
ConcatExpr* o = dynamic_cast<ConcatExpr*>(other.get());
if (o != nullptr) {
return e->equals(o->e) && f->equals(o->f);
}
return false;
}
};
class StarExpr : public RegularExpression {
public:
std::shared_ptr<RegularExpression> e;
StarExpr(std::shared_ptr<RegularExpression> e) : e(e) {}
std::shared_ptr<RegularExpression> simplify() override;
std::string sprintRE() override {
return "(" + e->sprintRE() + ")*";
}
bool equals(std::shared_ptr<RegularExpression> other) override {
StarExpr* o = dynamic_cast<StarExpr*>(other.get());
if (o != nullptr) {
return e->equals(o->e);
}
return false;
}
};
std::shared_ptr<RegularExpression> UnionExpr::simplify() {
auto se = e->simplify();
auto sf = f->simplify();
if (se->equals(sf)) {
return se;
} else if (dynamic_cast<EmptyExpr*>(se.get()) != nullptr) {
return sf;
} else if (dynamic_cast<EmptyExpr*>(sf.get()) != nullptr) {
return se;
} else {
return std::make_shared<UnionExpr>(se, sf);
}
}
std::shared_ptr<RegularExpression> ConcatExpr::simplify() {
auto se = e->simplify();
auto sf = f->simplify();
if (dynamic_cast<EpsilonExpr*>(se.get()) != nullptr) {
return sf;
} else if (dynamic_cast<EpsilonExpr*>(sf.get()) != nullptr) {
return se;
} else if (dynamic_cast<EmptyExpr*>(se.get()) != nullptr || dynamic_cast<EmptyExpr*>(sf.get()) != nullptr) {
return std::make_shared<EmptyExpr>();
} else {
return std::make_shared<ConcatExpr>(se, sf);
}
}
std::shared_ptr<RegularExpression> StarExpr::simplify() {
auto se = e->simplify();
if (dynamic_cast<EmptyExpr*>(se.get()) != nullptr || dynamic_cast<EpsilonExpr*>(se.get()) != nullptr) {
return std::make_shared<EpsilonExpr>();
} else {
return std::make_shared<StarExpr>(se);
}
}
std::shared_ptr<RegularExpression> recursiveSimplify(std::shared_ptr<RegularExpression> expr, int depth) {
if (depth > 200) {
return expr;
} else {
auto simplified = expr->simplify();
if (simplified->equals(expr)) {
return simplified;
} else {
return recursiveSimplify(simplified, depth + 1);
}
}
}
std::shared_ptr<RegularExpression> brzozowski(std::vector<std::vector<std::shared_ptr<RegularExpression>>>& a, std::vector<std::shared_ptr<RegularExpression>>& b) {
int m = a.size();
auto tempA = a;
auto tempB = b;
for (int n = m - 1; n >= 0; --n) {
tempB[n] = std::make_shared<ConcatExpr>(std::make_shared<StarExpr>(tempA[n][n]), tempB[n]);
for (int j = 0; j < n; ++j) {
tempA[n][j] = std::make_shared<ConcatExpr>(std::make_shared<StarExpr>(tempA[n][n]), tempA[n][j]);
}
for (int i = 0; i < n; ++i) {
tempB[i] = std::make_shared<UnionExpr>(tempB[i], std::make_shared<ConcatExpr>(tempA[i][n], tempB[n]));
for (int j = 0; j < n; ++j) {
tempA[i][j] = std::make_shared<UnionExpr>(tempA[i][j], std::make_shared<ConcatExpr>(tempA[i][n], tempA[n][j]));
}
}
for (int i = 0; i < n; ++i) {
tempA[i][n] = std::make_shared<EmptyExpr>();
}
}
return tempB[0];
}
int main() {
// Define the NFA transition matrix a
std::vector<std::vector<std::shared_ptr<RegularExpression>>> a(3, std::vector<std::shared_ptr<RegularExpression>>(3));
a[0][0] = std::make_shared<EmptyExpr>();
a[0][1] = std::make_shared<CarExpr>('a');
a[0][2] = std::make_shared<CarExpr>('b');
a[1][0] = std::make_shared<CarExpr>('b');
a[1][1] = std::make_shared<EmptyExpr>();
a[1][2] = std::make_shared<CarExpr>('a');
a[2][0] = std::make_shared<CarExpr>('a');
a[2][1] = std::make_shared<CarExpr>('b');
a[2][2] = std::make_shared<EmptyExpr>();
// Define the initial state vector b
std::vector<std::shared_ptr<RegularExpression>> b(3);
b[0] = std::make_shared<EpsilonExpr>();
b[1] = std::make_shared<EmptyExpr>();
b[2] = std::make_shared<EmptyExpr>();
// Apply Brzozowski's algorithm
auto dfaExpr = brzozowski(a, b);
// Print the regular expression
std::cout << dfaExpr->sprintRE() << "\n\n";
// Apply recursive simplification
auto simplifiedDFA = recursiveSimplify(dfaExpr, 0);
std::cout << simplifiedDFA->sprintRE() << std::endl;
return 0;
}
FreeBASIC
Type RegularExpression Extends Object
tipo As Integer
Declare Virtual Function toString() As String
Declare Virtual Function equals(other As RegularExpression Ptr) As Boolean
End Type
Function RegularExpression.toString() As String
Return ""
End Function
Function RegularExpression.equals(other As RegularExpression Ptr) As Boolean
Return tipo = other->tipo
End Function
Type EmptyExpr Extends RegularExpression
Declare Constructor()
Declare Virtual Function toString() As String
End Type
Constructor EmptyExpr()
tipo = 1
End Constructor
Function EmptyExpr.toString() As String
Return "0"
End Function
Type EpsilonExpr Extends RegularExpression
Declare Constructor()
Declare Virtual Function toString() As String
End Type
Constructor EpsilonExpr()
tipo = 2
End Constructor
Function EpsilonExpr.toString() As String
Return "1"
End Function
Type CarExpr Extends RegularExpression
c As String
Declare Constructor(ch As String)
Declare Virtual Function toString() As String
Declare Virtual Function equals(other As RegularExpression Ptr) As Boolean
End Type
Constructor CarExpr(ch As String)
tipo = 3
c = ch
End Constructor
Function CarExpr.toString() As String
Return c
End Function
Function CarExpr.equals(other As RegularExpression Ptr) As Boolean
Return other->tipo = 3 Andalso Cast(CarExpr Ptr, other)->c = c
End Function
Type UnionExpr Extends RegularExpression
e As RegularExpression Ptr : f As RegularExpression Ptr
Declare Constructor(e1 As RegularExpression Ptr, f1 As RegularExpression Ptr)
Declare Virtual Function toString() As String
Declare Virtual Function equals(other As RegularExpression Ptr) As Boolean
End Type
Constructor UnionExpr(e1 As RegularExpression Ptr, f1 As RegularExpression Ptr)
tipo = 4
e = e1
f = f1
End Constructor
Function UnionExpr.toString() As String
Return e->toString() & "+" & f->toString()
End Function
Function UnionExpr.equals(other As RegularExpression Ptr) As Boolean
If other->tipo <> 4 Then Return False
Dim As UnionExpr Ptr otherUnion = Cast(UnionExpr Ptr, other)
Return e->equals(otherUnion->e) AndAlso f->equals(otherUnion->f)
End Function
Type ConcatExpr Extends RegularExpression
e As RegularExpression Ptr
f As RegularExpression Ptr
Declare Constructor(e1 As RegularExpression Ptr, f1 As RegularExpression Ptr)
Declare Virtual Function toString() As String
Declare Virtual Function equals(other As RegularExpression Ptr) As Boolean
End Type
Constructor ConcatExpr(e1 As RegularExpression Ptr, f1 As RegularExpression Ptr)
tipo = 5
e = e1
f = f1
End Constructor
Function ConcatExpr.toString() As String
Return "(" & e->toString() & ")(" & f->toString() & ")"
End Function
Function ConcatExpr.equals(other As RegularExpression Ptr) As Boolean
If other->tipo <> 5 Then Return False
Dim As ConcatExpr Ptr otherConcat = Cast(ConcatExpr Ptr, other)
Return e->equals(otherConcat->e) AndAlso f->equals(otherConcat->f)
End Function
Type StarExpr Extends RegularExpression
e As RegularExpression Ptr
Declare Constructor(e1 As RegularExpression Ptr)
Declare Virtual Function toString() As String
Declare Virtual Function equals(other As RegularExpression Ptr) As Boolean
End Type
Constructor StarExpr(e1 As RegularExpression Ptr)
tipo = 6
e = e1
End Constructor
Function StarExpr.toString() As String
Return "(" & e->toString() & ")*"
End Function
Function StarExpr.equals(other As RegularExpression Ptr) As Boolean
Return other->tipo = 6 Andalso Cast(StarExpr Ptr, other)->e->equals(e)
End Function
Dim Shared As RegularExpression Ptr emptyRE, epsilonRE
Function brzozowski(a() As RegularExpression Ptr, b() As RegularExpression Ptr) As RegularExpression Ptr
Dim As Integer m, n, j, i
m = Ubound(a, 1) + 1
For n = m-1 To 0 Step -1
b(n) = New ConcatExpr(New StarExpr(a(n,n)), b(n))
For j = 0 To n-1
a(n,j) = New ConcatExpr(New StarExpr(a(n,n)), a(n,j))
Next
For i = 0 To n-1
b(i) = New UnionExpr(b(i), New ConcatExpr(a(i,n), b(n)))
For j = 0 To n-1
a(i,j) = New UnionExpr(a(i,j), New ConcatExpr(a(i,n), a(n,j)))
Next
Next
For i = 0 To n-1
a(i,n) = emptyRE
Next
Next
Return b(0)
End Function
Function simplifyExpression(e As RegularExpression Ptr, isTopLevel As Boolean = True) As RegularExpression Ptr
If isTopLevel Then
Dim As RegularExpression Ptr prevExpr = 0
Do
prevExpr = e
e = simplifyExpression(e, False)
Loop Until e->equals(prevExpr)
Return e
End If
Select Case e->tipo
Case 4 ' UnionExpr
Dim As UnionExpr Ptr u = Cast(UnionExpr Ptr, e)
Dim As RegularExpression Ptr ee = simplifyExpression(u->e, False)
Dim As RegularExpression Ptr ef = simplifyExpression(u->f, False)
If ee->equals(ef) Then Return ee
If ee->tipo = 4 Then
Dim As UnionExpr Ptr ue = Cast(UnionExpr Ptr, ee)
Return simplifyExpression(New UnionExpr(ue->e, New UnionExpr(ue->f, ef)), False)
End If
If ee->tipo = 1 Then Return ef
If ef->tipo = 1 Then Return ee
Return New UnionExpr(ee, ef)
Case 5 ' ConcatExpr
Dim As ConcatExpr Ptr c = Cast(ConcatExpr Ptr, e)
Dim As RegularExpression Ptr ee = simplifyExpression(c->e, False)
Dim As RegularExpression Ptr ef = simplifyExpression(c->f, False)
If ee->tipo = 2 Then Return ef
If ef->tipo = 2 Then Return ee
If ee->tipo = 1 Or ef->tipo = 1 Then Return emptyRE
If ee->tipo = 5 Then
Dim As ConcatExpr Ptr ce = Cast(ConcatExpr Ptr, ee)
Return simplifyExpression(New ConcatExpr(ce->e, New ConcatExpr(ce->f, ef)), False)
End If
Return New ConcatExpr(ee, ef)
Case 6 ' StarExpr
Dim As StarExpr Ptr s = Cast(StarExpr Ptr, e)
Dim As RegularExpression Ptr ee = simplifyExpression(s->e, False)
If ee->tipo = 1 Or ee->tipo = 2 Then Return epsilonRE
Return New StarExpr(ee)
End Select
Return e
End Function
' Main program
emptyRE = New EmptyExpr()
epsilonRE = New EpsilonExpr()
Dim As RegularExpression Ptr a(2,2)
a(0,0) = emptyRE : a(0,1) = New CarExpr("a") : a(0,2) = New CarExpr("b")
a(1,0) = New CarExpr("b"): a(1,1) = emptyRE : a(1,2) = New CarExpr("a")
a(2,0) = New CarExpr("a"): a(2,1) = New CarExpr("b") : a(2,2) = emptyRE
Dim As RegularExpression Ptr b(2) = {epsilonRE, emptyRE, emptyRE}
Dim As RegularExpression Ptr result = brzozowski(a(), b())
Print result->toString()
Print !"\nwhich simplifies to:\n"
Print simplifyExpression(result)->toString()
Sleep
- Output:
Same as Wren entry.
Go
package main
import (
"fmt"
)
type RE interface {
Equal(other RE) bool
String() string
}
type Empty struct{}
func (e Empty) String() string {
return "0"
}
func (e Empty) Equal(other RE) bool {
_, ok := other.(Empty)
return ok
}
type Epsilon struct{}
func (e Epsilon) String() string {
return "1"
}
func (e Epsilon) Equal(other RE) bool {
_, ok := other.(Epsilon)
return ok
}
type Car struct {
c string
}
func (e Car) String() string {
return e.c
}
func (e Car) Equal(other RE) bool {
o, ok := other.(Car)
return ok && e.c == o.c
}
type Union struct {
e RE
f RE
}
func (u Union) String() string {
return fmt.Sprintf("%s+%s", u.e.String(), u.f.String())
}
func (u Union) Equal(other RE) bool {
o, ok := other.(Union)
return ok && u.e.Equal(o.e) && u.f.Equal(o.f)
}
type Concat struct {
e RE
f RE
}
func (c Concat) String() string {
return fmt.Sprintf("(%s)(%s)", c.e.String(), c.f.String())
}
func (c Concat) Equal(other RE) bool {
o, ok := other.(Concat)
return ok && c.e.Equal(o.e) && c.f.Equal(o.f)
}
type Star struct {
e RE
}
func (s Star) String() string {
return fmt.Sprintf("(%s)*", s.e.String())
}
func (s Star) Equal(other RE) bool {
o, ok := other.(Star)
return ok && s.e.Equal(o.e)
}
var empty Empty
var epsilon Epsilon
func simple_re(e RE) RE {
for {
new_e := simple(e)
if new_e.Equal(e) {
break
}
e = new_e
}
return e
}
func simple(e RE) RE {
switch e := e.(type) {
case Union:
e_e := simple(e.e)
e_f := simple(e.f)
if e_e.Equal(e_f) {
return e_e
} else if e_e_union, ok := e_e.(Union); ok {
return simple(Union{e_e_union.e, Union{e_e_union.f, e_f}})
} else if e_e.Equal(empty) {
return e_f
} else if e_f.Equal(empty) {
return e_e
} else {
return Union{e_e, e_f}
}
case Concat:
e_e := simple(e.e)
e_f := simple(e.f)
if e_e.Equal(epsilon) {
return e_f
} else if e_f.Equal(epsilon) {
return e_e
} else if e_e.Equal(empty) || e_f.Equal(empty) {
return empty
} else if e_e_concat, ok := e_e.(Concat); ok {
return simple(Concat{e_e_concat.e, Concat{e_e_concat.f, e_f}})
} else {
return Concat{e_e, e_f}
}
case Star:
e_e := simple(e.e)
if _, ok := e_e.(Empty); ok || e_e.Equal(epsilon) {
return epsilon
} else {
return Star{e_e}
}
default:
return e
}
}
func brzozowski(a [][]RE, b []RE) RE {
m := len(a)
for n := m - 1; n >= 0; n-- {
a_nn := a[n][n]
b[n] = Concat{Star{a_nn}, b[n]}
for j := 0; j < n; j++ {
a[n][j] = Concat{Star{a_nn}, a[n][j]}
}
for i := 0; i < n; i++ {
b[i] = Union{b[i], Concat{a[i][n], b[n]}}
for j := 0; j < n; j++ {
a[i][j] = Union{a[i][j], Concat{a[i][n], a[n][j]}}
}
}
for i := 0; i < n; i++ {
a[i][n] = empty
}
}
return b[0]
}
func main() {
a := [][]RE{
{empty, Car{"a"}, Car{"b"}},
{Car{"b"}, empty, Car{"a"}},
{Car{"a"}, Car{"b"}, empty},
}
b := []RE{epsilon, empty, empty}
re := brzozowski(a, b)
fmt.Println(re.String())
fmt.Println()
fmt.Println(simple_re(re).String())
}
Java
import java.util.Arrays;
public final class BrzozowskiAlgebraicMethod {
public static void main(String[] args) {
// Define the NFA transition matrix a
RegularExpression[][] a = new RegularExpression[][] {
{ new EmptyExpression(), new CarExpression('a'), new CarExpression('b') },
{ new CarExpression('b'), new EmptyExpression(), new CarExpression('a') },
{ new CarExpression('a'), new CarExpression('b'), new EmptyExpression() }
};
// Define the initial state vector b
RegularExpression[] b = new RegularExpression[]
{ new EpsilonExpression(), new EmptyExpression(), new EmptyExpression() };
// Apply Brzozowski's algorithm
RegularExpression dfaExpr = brzozowski(a, b);
// Print the regular expression
System.out.println(dfaExpr.display() + System.lineSeparator());
// Apply recursive simplification
RegularExpression simplifiedDFA = recursiveSimplify(dfaExpr, 0);
System.out.println(simplifiedDFA.display());
}
private static RegularExpression brzozowski(RegularExpression[][] a, RegularExpression[] b) {
// Copy the given arrays to avoid mutating them
RegularExpression[][] aa = Arrays.copyOf(a, a.length);
RegularExpression[] bb = Arrays.copyOf(b, b.length);
for ( int i = a.length - 1; i >= 0; i-- ) {
bb[i] = new ConcatExpression( new StarExpression(aa[i][i]), bb[i] );
for ( int j = 0; j < i; j++ ) {
aa[i][j] = new ConcatExpression( new StarExpression(aa[i][i]), aa[i][j] );
}
for ( int k = 0; k < i; k++ ) {
bb[k] = new UnionExpression( bb[k], new ConcatExpression(aa[k][i], bb[i]) );
for ( int m = 0; m < i; m++ ) {
aa[k][m] = new UnionExpression( aa[k][m], new ConcatExpression(aa[k][i], aa[i][m]) );
}
}
for ( int n = 0; n < i; n++ ) {
aa[n][i] = new EmptyExpression();
}
}
return bb[0];
}
private static RegularExpression recursiveSimplify(RegularExpression expression, int depth) {
if ( depth > 200 ) {
return expression;
}
RegularExpression simplified = expression.simplify();
if ( simplified.equals(expression) ) {
return simplified;
}
return recursiveSimplify(simplified, depth + 1);
}
private static abstract class RegularExpression {
protected abstract RegularExpression simplify();
protected abstract String display();
protected abstract boolean equals(RegularExpression other);
}
private static final class EmptyExpression extends RegularExpression {
@Override
protected RegularExpression simplify() {
return new EmptyExpression();
}
@Override
protected String display() {
return "0";
}
@Override
protected boolean equals(RegularExpression other) {
return switch ( other ) {
case EmptyExpression empty -> true;
case RegularExpression regular -> false;
};
}
}
private static final class EpsilonExpression extends RegularExpression {
@Override
protected RegularExpression simplify() {
return new EpsilonExpression();
}
@Override
protected String display() {
return "1";
}
@Override
protected boolean equals(RegularExpression other) {
return switch ( other ) {
case EpsilonExpression epsilon -> true;
case RegularExpression regular -> false;
};
}
}
private static final class CarExpression extends RegularExpression {
public CarExpression(char aChar) {
ch = aChar;
}
@Override
protected RegularExpression simplify() {
return new CarExpression(ch);
}
@Override
protected String display() {
return String.valueOf(ch);
}
@Override
protected boolean equals(RegularExpression other) {
return switch ( other ) {
case CarExpression car -> ch == car.ch;
case RegularExpression regular -> false;
};
}
private final char ch;
}
private static final class UnionExpression extends RegularExpression {
public UnionExpression(RegularExpression aE, RegularExpression aF) {
e = aE;
f = aF;
}
@Override
protected RegularExpression simplify() {
RegularExpression se = e.simplify();
RegularExpression sf = f.simplify();
if ( se.equals(sf) ) {
return se;
}
return switch ( se ) {
case UnionExpression uni -> new UnionExpression(uni.e, new UnionExpression(uni.f, sf));
case EmptyExpression empty -> sf;
case RegularExpression regular -> switch ( sf ) {
case EmptyExpression empty -> se;
case RegularExpression reg -> new UnionExpression(se, sf);
};
};
}
@Override
protected String display() {
return e.display() + "+" + f.display();
}
@Override
protected boolean equals(RegularExpression other) {
return switch ( other ) {
case UnionExpression union ->
// Since Union is commutative, check both orders of the parameters e and f
( e.equals(union.e) && f.equals(union.f) ) || ( e.equals(union.f) && f.equals(union.e) );
case RegularExpression regular -> false;
};
}
private final RegularExpression e, f;
}
private static final class ConcatExpression extends RegularExpression {
public ConcatExpression(RegularExpression aE, RegularExpression aF) {
e = aE;
f = aF;
}
@Override
protected RegularExpression simplify() {
RegularExpression se = e.simplify();
RegularExpression sf = f.simplify();
return switch ( se ) {
case EpsilonExpression epsilon -> sf;
case RegularExpression regular -> switch ( sf ) {
case EpsilonExpression epsilon -> se;
case EmptyExpression empty -> new EmptyExpression();
case RegularExpression reg -> switch ( se ) {
case EmptyExpression empty -> new EmptyExpression();
case ConcatExpression c -> new ConcatExpression(c.e, new ConcatExpression(c.f, sf));
case RegularExpression regula -> new ConcatExpression(se, sf);
};
};
};
}
@Override
protected String display() {
return "(" + e.display() + ")(" + f.display() + ")";
}
@Override
protected boolean equals(RegularExpression other) {
return switch ( other ) {
case UnionExpression union -> e.equals(union.e) && f.equals(union.f);
case RegularExpression regular -> false;
};
}
private final RegularExpression e, f;
}
private static final class StarExpression extends RegularExpression {
public StarExpression(RegularExpression aE) {
e = aE;
}
@Override
protected RegularExpression simplify() {
RegularExpression se = e.simplify();
return switch ( se ) {
case EmptyExpression empty -> new EpsilonExpression();
case EpsilonExpression epsilon -> new EpsilonExpression();
case RegularExpression regular -> new StarExpression(se);
};
}
@Override
protected String display() {
return "(" + e.display() + ")*";
}
@Override
protected boolean equals(RegularExpression other) {
return switch ( other ) {
case StarExpression star -> e.equals(star.e);
case RegularExpression regular -> false;
};
}
private final RegularExpression e;
}
}
JavaScript
class RE {
equals(other) {
return other instanceof this.constructor && this.dictEquals(other);
}
dictEquals(other) {
const keys1 = Object.keys(this);
const keys2 = Object.keys(other);
if (keys1.length !== keys2.length) return false;
for (let key of keys1) {
if (this[key] !== other[key]) return false;
}
return true;
}
}
class Empty extends RE {
toString() {
return "0";
}
}
const empty = new Empty();
class Epsilon extends RE {
toString() {
return "1";
}
}
const epsilon = new Epsilon();
class Car extends RE {
constructor(c) {
super();
this.c = c;
}
toString() {
return this.c;
}
equals(other) {
return other instanceof Car && this.c === other.c;
}
}
class Union extends RE {
constructor(e, f) {
super();
this.e = e;
this.f = f;
}
toString() {
return `${this.e}+${this.f}`;
}
equals(other) {
return other instanceof Union && this.e.equals(other.e) && this.f.equals(other.f);
}
}
class Concat extends RE {
constructor(e, f) {
super();
this.e = e;
this.f = f;
}
toString() {
return `(${this.e})(${this.f})`;
}
equals(other) {
return other instanceof Concat && this.e.equals(other.e) && this.f.equals(other.f);
}
}
class Star extends RE {
constructor(e) {
super();
this.e = e;
}
toString() {
return `(${this.e})*`;
}
equals(other) {
return other instanceof Star && this.e.equals(other.e);
}
}
function simpleRe(e) {
function simple(e) {
if (e instanceof Union) {
const e_e = simple(e.e);
const e_f = simple(e.f);
if (e_e.equals(e_f)) {
return e_e;
} else if (e_e.equals(empty)) {
return e_f;
} else if (e_f.equals(empty)) {
return e_e;
} else if (e_e instanceof Union) {
return simple(new Union(e_e.e, new Union(e_e.f, e_f)));
} else {
return new Union(e_e, e_f);
}
} else if (e instanceof Concat) {
const e_e = simple(e.e);
const e_f = simple(e.f);
if (e_e.equals(epsilon)) {
return e_f;
} else if (e_f.equals(epsilon)) {
return e_e;
} else if (e_e.equals(empty) || e_f.equals(empty)) {
return empty;
} else if (e_e instanceof Concat) {
return simple(new Concat(e_e.e, new Concat(e_e.f, e_f)));
} else {
return new Concat(e_e, e_f);
}
} else if (e instanceof Star) {
const e_e = simple(e.e);
if (e_e instanceof Empty || e_e instanceof Epsilon) {
return epsilon;
} else {
return new Star(e_e);
}
} else {
return e;
}
}
let prevE = null;
while (!e.equals(prevE)) {
prevE = e;
e = simple(e);
}
return e;
}
function brzozowski(a, b) {
const m = a.length;
for (let n = m - 1; n >= 0; n--) {
const a_nn = a[n][n];
b[n] = new Concat(new Star(a_nn), b[n]);
for (let j = 0; j < n; j++) {
a[n][j] = new Concat(new Star(a_nn), a[n][j]);
}
for (let i = 0; i < n; i++) {
b[i] = new Union(b[i], new Concat(a[i][n], b[n]));
for (let j = 0; j < n; j++) {
a[i][j] = new Union(a[i][j], new Concat(a[i][n], a[n][j]));
}
}
for (let i = 0; i < n; i++) {
a[i][n] = empty;
}
}
return b[0];
}
const a = [
[empty, new Car('a'), new Car('b')],
[new Car('b'), empty, new Car('a')],
[new Car('a'), new Car('b'), empty],
];
const b = [epsilon, empty, empty];
const re = brzozowski(a, b);
console.log(re.toString());
console.log();
console.log(simpleRe(re).toString());
Julia
import Base.==
import Base.string
abstract type RE end
struct Empty <: RE end
string(e::Empty) = "0"
const empty = Empty()
==(e1::Empty, e2::Empty) = true
struct Epsilon <: RE end
string(e::Epsilon) = "1"
const epsilon = Epsilon()
==(e1::Epsilon, e2::Epsilon) = true
struct Car <: RE
c::Any
end
string(c1::Car) = c1.c
==(c1::Car, c2::Car) = c1.c isa typeof(c2.c) && c1.c == c2.c
struct Union <: RE
e::Any
f::Any
end
string(u::Union) = string(u.e) * "+" * string(u.f)
==(u1::Union, u2::Union) =
u1.e isa typeof(u2.e) && u1.e == u2.e && u1.f isa typeof(u2.f) && u1.f == u2.f
struct Concat <: RE
e::Any
f::Any
end
string(c::Concat) = "(" * string(c.e) * ")(" * string(c.f) * ")"
==(c1::Concat, c2::Concat) =
c1.e isa typeof(c2.e) && c1.e == c2.e && c1.f isa typeof(c2.f) && c1.f == c2.f
struct Star <: RE
e::Any
end
string(s::Star) = "(" * string(s.e) * ")*"
==(s1::Star, s2::Star) = s1.e isa typeof(s2.e) && s1.e == s2.e
function simple_re(e)
function simple(e::Union)
e_e = simple(e.e)
e_f = simple(e.f)
e_e isa typeof(e_f) && e_e == e_f && return e_e
e_e isa Union && return simple(Union(e_e.e, Union(e_e.f, e_f)))
e_e isa Empty && return e_f
e_f isa Empty && return e_e
return Union(e_e, e_f)
end
function simple(e::Concat)
e_e = simple(e.e)
e_f = simple(e.f)
e_e isa Epsilon && return e_f
e_f isa Epsilon && return e_e
(e_e isa Empty || e_f isa Empty) && return empty
e_e isa Concat && return simple(Concat(e_e.e, Concat(e_e.f, e_f)))
return Concat(e_e, e_f)
end
function simple(e::Star)
e_e = simple(e.e)
(e_e isa Empty || e_e isa Epsilon) && return epsilon
return Star(e_e)
end
simple(e) = e # default
while true
prevE = e
e = simple(e)
e isa typeof(prevE) && e == prevE && break
end
return e
end
function brzozowski!(a, b)
for n = length(a):-1:1
a_nn = a[n][n]
b[n] = Concat(Star(a_nn), b[n])
for j = 1:n-1
a[n][j] = Concat(Star(a_nn), a[n][j])
end
for i = 1:n-1
b[i] = Union(b[i], Concat(a[i][n], b[n]))
for j = 1:n-1
a[i][j] = Union(a[i][j], Concat(a[i][n], a[n][j]))
end
end
for i = 1:n-1
a[i][n] = empty
end
end
return b[begin]
end
const a =
[[empty, Car("a"), Car("b")], [Car("b"), empty, Car("a")], [Car("a"), Car("b"), empty]]
const b = [epsilon, empty, empty]
const re = brzozowski!(a, b)
println(string(re))
println("\nwhich simplifies to:\n")
println(string(simple_re(re)))
- Output:
((0+(b)(((0)*)(a))+(a+(b)(((0)*)(b)))(((0+(a)(((0)*)(b)))*)(b+(a)(((0)*)(a)))))*)(1+(b)(((0)*)(0))+(a+(b)(((0)*)(b)))(((0+(a)(((0)*)(b)))*)(0+(a)(((0)*)(0))))) which simplifies to: ((b)(a)+(a+(b)(b))((((a)(b))*)(b+(a)(a))))*
Mathematica /Wolfram Language
(* Define regular expression types *)
Clear[EmptyExpr, EpsilonExpr, CarExpr, UnionExpr, ConcatExpr, StarExpr]
(* Simplify regular expressions using simplifications similar to OCaml's simple_re *)
Clear[simplify]
(* Simplify each type of regular expression *)
simplify[EmptyExpr[]] := EmptyExpr[]
simplify[EpsilonExpr[]] := EpsilonExpr[]
simplify[CarExpr[c_]] := CarExpr[c]
(* Simplify Union of expressions, accounting for EmptyExpr and redundant unions *)
simplify[UnionExpr[e_, f_]] :=
If[e === f,
e,
(* Simplify Union with EmptyExpr *)
If[e === EmptyExpr[],
simplify[f],
If[f === EmptyExpr[],
simplify[e],
UnionExpr[simplify[e], simplify[f]]
]
]
]
(* Simplify Concat of expressions *)
simplify[ConcatExpr[e_, f_]] :=
Which[
e === EpsilonExpr[], f,
f === EpsilonExpr[], e,
e === EmptyExpr[], EmptyExpr[],
f === EmptyExpr[], EmptyExpr[],
True, ConcatExpr[simplify[e], simplify[f]]
]
(* Simplify Star of expressions *)
simplify[StarExpr[EmptyExpr[]]] := EpsilonExpr[]
simplify[StarExpr[EpsilonExpr[]]] := EpsilonExpr[]
simplify[StarExpr[e_]] := StarExpr[simplify[e]]
(* Ensure the simplified expression is reduced as much as possible *)
simplify[expr_] := expr
(* Recursively simplify with a limit on depth to avoid infinite recursion *)
Clear[recursiveSimplify]
recursiveSimplify[expr_, depth_Integer] := Module[{simplified},
(* If we've reached a maximum depth, stop the recursion *)
If[depth > 200,
Return[expr],
simplified = simplify[expr];
If[simplified === expr,
simplified,
recursiveSimplify[simplified, depth + 1]
]
]
]
(* String representation of the regular expression *)
Clear[sprintRE]
sprintRE[EmptyExpr[]] := "0"
sprintRE[EpsilonExpr[]] := "1"
sprintRE[CarExpr[c_]] := ToString[c]
sprintRE[UnionExpr[e_, f_]] := sprintRE[e] <> "+" <> sprintRE[f]
sprintRE[ConcatExpr[e_, f_]] := "(" <> sprintRE[e] <> ")(" <> sprintRE[f] <> ")"
sprintRE[StarExpr[e_]] := "(" <> sprintRE[e] <> ")*"
(* Brzozowski's Algorithm for NFA to DFA conversion *)
Clear[brzozowski]
brzozowski[a_, b_] := Module[{m, n, i, j, tempA, tempB},
m = Length[a];
(* Initialize the result matrix b as an empty DFA transition matrix *)
tempA = a;
tempB = b;
Do[
(* Process each state in reverse order *)
tempB[[n]] = ConcatExpr[StarExpr[tempA[[n, n]]], tempB[[n]]];
Do[
(* Update the NFA transition matrix tempA *)
tempA[[n, j]] = ConcatExpr[StarExpr[tempA[[n, n]]], tempA[[n, j]]];
, {j, 1, n - 1}];
Do[
tempB[[i]] = UnionExpr[tempB[[i]], ConcatExpr[tempA[[i, n]], tempB[[n]]]];
Do[
tempA[[i, j]] = UnionExpr[
tempA[[i, j]],
ConcatExpr[tempA[[i, n]], tempA[[n, j]]]
];
, {j, 1, n - 1}];
, {i, 1, n - 1}];
Do[
tempA[[i, n]] = EmptyExpr[];
, {i, 1, n - 1}];
, {n, m, 1, -1}];
(* Return the regular expression for the DFA starting from state 0 *)
tempB[[1]]
]
(* Define an example NFA transition matrix *)
a = {
{EmptyExpr[], CarExpr["a"], CarExpr["b"]},
{CarExpr["b"], EmptyExpr[], CarExpr["a"]},
{CarExpr["a"], CarExpr["b"], EmptyExpr[]}
};
b = {EpsilonExpr[], EmptyExpr[], EmptyExpr[]};
(* Convert NFA to DFA using Brzozowski's algorithm *)
dfaExpr = brzozowski[a, b];
Print[sprintRE@dfaExpr, "\n"];
(* Apply recursive simplification and print the simplified result *)
simplifiedDFA = recursiveSimplify[dfaExpr, 0];
Print[sprintRE[simplifiedDFA]]
Phix
constant empty = "0",
epsilon = "1"
// [confuse not with union builtin]
function onion(object a, b) return {a,"+",b} end function
function concat(object a, b) return {"(",a,")(",b,")"} end function
function star(object a) return {"(",a,")*"} end function
function is_onion(sequence e) return not string(e) and e[2]="+" end function
function is_concat(sequence e) return not string(e) and e[3]=")(" end function
function is_star(sequence e) return not string(e) and e[3]=")*" end function
function brzozowski(sequence a, b)
for n=length(a) to 1 by -1 do
object star_ann = star(a[n,n])
b[n] = concat(star_ann, b[n])
for j=1 to n-1 do
a[n,j] = concat(star_ann, a[n,j])
end for
for i=1 to n-1 do
b[i] = onion(b[i], concat(a[i,n], b[n]))
for j=1 to n-1 do
a[i,j] = onion(a[i,j], concat(a[i,n], a[n,j]))
end for
end for
end for
return b[1]
end function
function re_to_string(object o)
if not string(o) then
for i,oi in o do
o[i] = re_to_string(oi)
end for
o = join(o,"")
end if
return o
end function
function simple(object e)
if not string(e) then
if is_onion(e) then
object lhs = simple(e[1]),
rhs = simple(e[3])
if lhs=empty then return rhs end if
if lhs=rhs or rhs=empty then return lhs end if
if is_onion(lhs) then return simple(onion(lhs[1],onion(lhs[3],rhs))) end if
return onion(lhs,rhs)
elsif is_concat(e) then
object lhs = simple(e[2]),
rhs = simple(e[4])
if lhs=epsilon then return rhs end if
if rhs=epsilon then return lhs end if
if lhs=empty or rhs=empty then return empty end if
if is_concat(lhs) then return simple(concat(lhs[2],concat(lhs[4],rhs))) end if
return concat(lhs,rhs)
else
assert(is_star(e))
object f = simple(e[2])
if f=empty or f=epsilon then return epsilon end if
return star(f)
end if
end if
return e
end function
function simplify(object e)
do
object prev = e
e = simple(e)
until e = prev
return e
end function
constant a = {{empty,"a","b"},
{"b",empty,"a"},
{"a","b",empty}},
b = {epsilon,empty,empty},
re = brzozowski(a, b),
s = simplify(re)
printf(1,"%s\n\n which simplifies to:\n\n%s\n",{re_to_string(re),
re_to_string(s)})
- Output:
((0+(b)(((0)*)(a))+(a+(b)(((0)*)(b)))(((0+(a)(((0)*)(b)))*)(b+(a)(((0)*)(a)))))*)(1+(b)(((0)*)(0))+(a+(b)(((0)*)(b)))(((0+(a)(((0)*)(b)))*)(0+(a)(((0)*)(0))))) which simplifies to: ((b)(a)+(a+(b)(b))((((a)(b))*)(b+(a)(a))))*
Python
class RE:
def __eq__(self, other):
return isinstance(other, type(self)) and self.__dict__ == other.__dict__
class Empty(RE):
def __str__(self):
return "0"
empty = Empty()
class Epsilon(RE):
def __str__(self):
return "1"
epsilon = Epsilon()
class Car(RE):
def __init__(self, c):
self.c = c
def __str__(self):
return self.c
def __eq__(self, other):
return isinstance(other, Car) and self.c == other.c
class Union(RE):
def __init__(self, e, f):
self.e = e
self.f = f
def __str__(self):
return f"{self.e}+{self.f}"
def __eq__(self, other):
return isinstance(other, Union) and self.e == other.e and self.f == other.f
class Concat(RE):
def __init__(self, e, f):
self.e = e
self.f = f
def __str__(self):
return f"({self.e})({self.f})"
def __eq__(self, other):
return isinstance(other, Concat) and self.e == other.e and self.f == other.f
class Star(RE):
def __init__(self, e):
self.e = e
def __str__(self):
return f"({self.e})*"
def __eq__(self, other):
return isinstance(other, Star) and self.e == other.e
def simple_re(e):
def simple(e):
if isinstance(e, Union):
e_e = simple(e.e)
e_f = simple(e.f)
if e_e == e_f:
return e_e
elif isinstance(e_e, Union):
return simple(Union(e_e.e, Union(e_e.f, e_f)))
elif e_e == empty:
return e_f
elif e_f == empty:
return e_e
else:
return Union(e_e, e_f)
elif isinstance(e, Concat):
e_e = simple(e.e)
e_f = simple(e.f)
if e_e == epsilon:
return e_f
elif e_f == epsilon:
return e_e
elif e_e == empty or e_f == empty:
return empty
elif isinstance(e_e, Concat):
return simple(Concat(e_e.e, Concat(e_e.f, e_f)))
else:
return Concat(e_e, e_f)
elif isinstance(e, Star):
e_e = simple(e.e)
if isinstance(e_e, Empty) or isinstance(e_e, Epsilon):
return epsilon
else:
return Star(e_e)
else:
return e
prev_e = None
while e != prev_e:
prev_e = e
e = simple(e)
return e
def brzozowski(a, b):
m = len(a)
for n in range(m-1, -1, -1):
a_nn = a[n][n]
b[n] = Concat(Star(a_nn), b[n])
for j in range(n):
a[n][j] = Concat(Star(a_nn), a[n][j])
for i in range(n):
b[i] = Union(b[i], Concat(a[i][n], b[n]))
for j in range(n):
a[i][j] = Union(a[i][j], Concat(a[i][n], a[n][j]))
for i in range(n):
a[i][n] = empty
return b[0]
a = [
[empty, Car('a'), Car('b')],
[Car('b'), empty, Car('a')],
[Car('a'), Car('b'), empty],
]
b = [epsilon, empty, empty]
re = brzozowski(a, b)
print(str(re))
print()
print(str(simple_re(re)))
R
# Define regular expression types
EmptyExpr <- function() list(type = 'EmptyExpr')
EpsilonExpr <- function() list(type = 'EpsilonExpr')
CarExpr <- function(c) list(type = 'CarExpr', c = c)
UnionExpr <- function(e, f) list(type = 'UnionExpr', e = e, f = f)
ConcatExpr <- function(e, f) list(type = 'ConcatExpr', e = e, f = f)
StarExpr <- function(e) list(type = 'StarExpr', e = e)
# Simplify regular expressions
simplify <- function(expr) {
if (expr$type == 'EmptyExpr') {
expr
} else if (expr$type == 'EpsilonExpr') {
expr
} else if (expr$type == 'CarExpr') {
expr
} else if (expr$type == 'UnionExpr') {
e <- simplify(expr$e)
f <- simplify(expr$f)
if (identical(e, f)) {
e
} else if (e$type == 'EmptyExpr') {
f
} else if (f$type == 'EmptyExpr') {
e
} else {
list(type = 'UnionExpr', e = e, f = f)
}
} else if (expr$type == 'ConcatExpr') {
e <- simplify(expr$e)
f <- simplify(expr$f)
if (e$type == 'EpsilonExpr') {
f
} else if (f$type == 'EpsilonExpr') {
e
} else if (e$type == 'EmptyExpr' || f$type == 'EmptyExpr') {
EmptyExpr()
} else {
list(type = 'ConcatExpr', e = e, f = f)
}
} else if (expr$type == 'StarExpr') {
e <- simplify(expr$e)
if (e$type == 'EmptyExpr' || e$type == 'EpsilonExpr') {
EpsilonExpr()
} else {
list(type = 'StarExpr', e = e)
}
} else {
expr
}
}
# Recursively simplify expressions with depth limit
recursiveSimplify <- function(expr, depth) {
if (depth > 200) {
return(expr)
} else {
simplified <- simplify(expr)
if (identical(simplified, expr)) {
return(simplified)
} else {
recursiveSimplify(simplified, depth + 1)
}
}
}
# String representation of the regular expression
sprintRE <- function(expr) {
if (expr$type == 'EmptyExpr') {
"0"
} else if (expr$type == 'EpsilonExpr') {
"1"
} else if (expr$type == 'CarExpr') {
as.character(expr$c)
} else if (expr$type == 'UnionExpr') {
paste0(sprintRE(expr$e), "+", sprintRE(expr$f))
} else if (expr$type == 'ConcatExpr') {
paste0("(", sprintRE(expr$e), ")(", sprintRE(expr$f), ")")
} else if (expr$type == 'StarExpr') {
paste0("(", sprintRE(expr$e), ")*")
} else {
""
}
}
# Brzozowski's Algorithm for NFA to DFA conversion
brzozowski <- function(a, b) {
m <- length(a)
tempA <- a
tempB <- b
for (n in seq(m, 1)) {
tempB[[n]] <- (ConcatExpr(StarExpr(tempA[[n]][[n]]), tempB[[n]]))
for (j in seq_len(n - 1)) {
tempA[[n]][[j]] <- (ConcatExpr(StarExpr(tempA[[n]][[n]]), tempA[[n]][[j]]))
}
for (i in seq_len(n - 1)) {
tempB[[i]] <- (UnionExpr(tempB[[i]], ConcatExpr(tempA[[i]][[n]], tempB[[n]])))
for (j in seq_len(n - 1)) {
tempA[[i]][[j]] <- (UnionExpr(
tempA[[i]][[j]],
ConcatExpr(tempA[[i]][[n]], tempA[[n]][[j]])
))
}
}
for (i in seq_len(n - 1)) {
tempA[[i]][[n]] <- EmptyExpr()
}
}
tempB[[1]]
}
# Define an example NFA transition matrix
a <- list(
list(EmptyExpr(), CarExpr("a"), CarExpr("b")),
list(CarExpr("b"), EmptyExpr(), CarExpr("a")),
list(CarExpr("a"), CarExpr("b"), EmptyExpr())
)
b <- list(EpsilonExpr(), EmptyExpr(), EmptyExpr())
# Convert NFA to DFA using Brzozowski's algorithm
dfaExpr <- brzozowski(a, b)
cat(sprintRE(dfaExpr), "\n\n", sep="")
# Apply recursive simplification and print the simplified result
simplifiedDFA <- recursiveSimplify(dfaExpr, 0)
cat(sprintRE(simplifiedDFA), "\n", sep="")
Raku
# 20241120 Raku programming solution
role RE1 { has $.c }
role RE2 { has ( $.e, $.f ) }
class Empty { method Str { '0' } }
class Epsilon { method Str { '1' } }
class Car does RE1 { method Str { $.c } } # Caractère ?
class Star does RE1 { method Str { "($.c)*" } }
class Union does RE2 { method Str { "$.e+$.f" } }
class Concat does RE2 { method Str { "($.e)($.f)" } }
my ($empty, $epsilon) = (Empty, Epsilon)>>.new;
sub simple-re($e is rw) {
sub do-simple($e) {
given $e {
when Union {
my ($ee,$ef) = ($e.e, $e.f).map: { do-simple $_ };
if $ee ~~ $ef { return $ee }
elsif $ee ~~ Union { do-simple(Union.new(e => $ee.e, f => Union.new(e => $ee.f, f => $ef))) }
elsif $ee ~~ Empty { return $ef }
elsif $ef ~~ Empty { return $ee }
else { Union.new: e => $ee, f => $ef }
}
when Concat {
my ($ee,$ef) = ($e.e, $e.f).map: { do-simple $_ };
if $ee ~~ Epsilon { return $ef }
elsif $ef ~~ Epsilon { return $ee }
elsif $ee ~~ Empty || $ef ~~ Empty { return Empty }
elsif $ee ~~ Concat { do-simple(Concat.new(e => $ee.e, f => Concat.new(e => $ee.f, f => $ef))) }
else { Concat.new: e => $ee, f => $ef }
}
when Star {
given do-simple($e.c) {
$_ ~~ Empty | Epsilon ?? return Epsilon !! Star.new: c => $_
}
}
default { $e }
}
}
my $prev = '';
until $e === $prev or $e.Str eq $prev { ($prev, $e) = $e, do-simple($e) }
return $e;
}
sub brzozowski(@a, @b) {
for @a.elems - 1 ... 0 -> \n {
@b[n] = Concat.new(e => Star.new(c => @a[n;n]), f => @b[n]);
for ^n -> \j {
@a[n;j] = Concat.new(e => Star.new(c => @a[n;n]), f => @a[n;j]);
}
for ^n -> \i {
@b[i] = Union.new(e => @b[i], f => Concat.new(e => @a[i;n], f => @b[n]));
for ^n -> \j {
@a[i;j] = Union.new(e => @a[i;j], f => Concat.new(e => @a[i;n], f => @a[n;j]));
}
}
for ^n -> \i { @a[i;n] = $empty }
}
return @b[0]
}
my @a = [
[$empty, Car.new(c => 'a'), Car.new(c => 'b')],
[Car.new(c => 'b'), $empty, Car.new(c => 'a')],
[Car.new(c => 'a'), Car.new(c => 'b'), $empty],
];
my @b = [$epsilon, $empty, $empty];
say ( my $re = brzozowski(@a, @b) ).Str;
say simple-re($re).Str;
You may Attempt This Online!
Rust
//use std::fmt;
#[derive(Clone)]
enum RegularExpression {
EmptyExpr,
EpsilonExpr,
CarExpr(char),
UnionExpr(Box<RegularExpression>, Box<RegularExpression>),
ConcatExpr(Box<RegularExpression>, Box<RegularExpression>),
StarExpr(Box<RegularExpression>),
}
impl RegularExpression {
fn simplify(&self) -> RegularExpression {
match self {
RegularExpression::EmptyExpr => RegularExpression::EmptyExpr,
RegularExpression::EpsilonExpr => RegularExpression::EpsilonExpr,
RegularExpression::CarExpr(c) => RegularExpression::CarExpr(*c),
RegularExpression::UnionExpr(e, f) => {
let se = e.simplify();
let sf = f.simplify();
if se.equals(&sf) {
se
} else if se.is_empty() {
sf
} else if sf.is_empty() {
se
} else {
RegularExpression::UnionExpr(Box::new(se), Box::new(sf))
}
}
RegularExpression::ConcatExpr(e, f) => {
let se = e.simplify();
let sf = f.simplify();
if se.is_epsilon() {
sf
} else if sf.is_epsilon() {
se
} else if se.is_empty() || sf.is_empty() {
RegularExpression::EmptyExpr
} else {
RegularExpression::ConcatExpr(Box::new(se), Box::new(sf))
}
}
RegularExpression::StarExpr(e) => {
let se = e.simplify();
if se.is_empty() || se.is_epsilon() {
RegularExpression::EpsilonExpr
} else {
RegularExpression::StarExpr(Box::new(se))
}
}
}
}
fn sprint_re(&self) -> String {
match self {
RegularExpression::EmptyExpr => "0".to_string(),
RegularExpression::EpsilonExpr => "1".to_string(),
RegularExpression::CarExpr(c) => c.to_string(),
RegularExpression::UnionExpr(e, f) => format!("{}+{}", e.sprint_re(), f.sprint_re()),
RegularExpression::ConcatExpr(e, f) => {
format!("({})({})", e.sprint_re(), f.sprint_re())
}
RegularExpression::StarExpr(e) => format!("({})*", e.sprint_re()),
}
}
fn equals(&self, other: &RegularExpression) -> bool {
match (self, other) {
(RegularExpression::EmptyExpr, RegularExpression::EmptyExpr) => true,
(RegularExpression::EpsilonExpr, RegularExpression::EpsilonExpr) => true,
(RegularExpression::CarExpr(c1), RegularExpression::CarExpr(c2)) => c1 == c2,
(RegularExpression::UnionExpr(e1, f1), RegularExpression::UnionExpr(e2, f2)) => {
(e1.equals(e2) && f1.equals(f2)) || (e1.equals(f2) && f1.equals(e2))
}
(RegularExpression::ConcatExpr(e1, f1), RegularExpression::ConcatExpr(e2, f2)) => {
e1.equals(e2) && f1.equals(f2)
}
(RegularExpression::StarExpr(e1), RegularExpression::StarExpr(e2)) => e1.equals(e2),
_ => false,
}
}
fn is_empty(&self) -> bool {
matches!(self, RegularExpression::EmptyExpr)
}
fn is_epsilon(&self) -> bool {
matches!(self, RegularExpression::EpsilonExpr)
}
}
fn recursive_simplify(expr: &RegularExpression, depth: usize) -> RegularExpression {
if depth > 200 {
expr.clone()
} else {
let simplified = expr.simplify();
if simplified.equals(expr) {
simplified
} else {
recursive_simplify(&simplified, depth + 1)
}
}
}
fn brzozowski(
a: &[Vec<RegularExpression>],
b: &[RegularExpression],
) -> RegularExpression {
let m = a.len();
let mut temp_a = a.to_vec();
let mut temp_b = b.to_vec();
for n in (0..m).rev() {
temp_b[n] = RegularExpression::ConcatExpr(
Box::new(RegularExpression::StarExpr(Box::new(temp_a[n][n].clone()))),
Box::new(temp_b[n].clone()),
);
for j in 0..n {
temp_a[n][j] = RegularExpression::ConcatExpr(
Box::new(RegularExpression::StarExpr(Box::new(temp_a[n][n].clone()))),
Box::new(temp_a[n][j].clone()),
);
}
for i in 0..n {
temp_b[i] = RegularExpression::UnionExpr(
Box::new(temp_b[i].clone()),
Box::new(RegularExpression::ConcatExpr(
Box::new(temp_a[i][n].clone()),
Box::new(temp_b[n].clone()),
)),
);
for j in 0..n {
temp_a[i][j] = RegularExpression::UnionExpr(
Box::new(temp_a[i][j].clone()),
Box::new(RegularExpression::ConcatExpr(
Box::new(temp_a[i][n].clone()),
Box::new(temp_a[n][j].clone()),
)),
);
}
}
for i in 0..n {
temp_a[i][n] = RegularExpression::EmptyExpr;
}
}
temp_b[0].clone()
}
fn main() {
// Define the NFA transition matrix a
let mut a = vec![vec![RegularExpression::EmptyExpr; 3]; 3];
a[0][0] = RegularExpression::EmptyExpr;
a[0][1] = RegularExpression::CarExpr('a');
a[0][2] = RegularExpression::CarExpr('b');
a[1][0] = RegularExpression::CarExpr('b');
a[1][1] = RegularExpression::EmptyExpr;
a[1][2] = RegularExpression::CarExpr('a');
a[2][0] = RegularExpression::CarExpr('a');
a[2][1] = RegularExpression::CarExpr('b');
a[2][2] = RegularExpression::EmptyExpr;
// Define the initial state vector b
let b = vec![
RegularExpression::EpsilonExpr,
RegularExpression::EmptyExpr,
RegularExpression::EmptyExpr,
];
// Apply Brzozowski's algorithm
let dfa_expr = brzozowski(&a, &b);
// Print the regular expression
println!("{}\n", dfa_expr.sprint_re());
// Apply recursive simplification
let simplified_dfa = recursive_simplify(&dfa_expr, 0);
println!("{}", simplified_dfa.sprint_re());
}
Wren
class RE {
// need to override if subtype has any fields
== (other) { this.type == other.type }
!= (other) { !(this == other) }
}
class Empty is RE {
construct new() {}
toString { "0" }
}
var empty = Empty.new()
class Epsilon is RE {
construct new() {}
toString { "1" }
}
var epsilon = Epsilon.new()
class Car is RE {
construct new(c) { _c = c }
c { _c }
toString { _c }
== (other) { (other is Car) && _c == other.c }
}
class Union is RE {
construct new(e, f) {
_e = e
_f = f
}
e { _e }
f { _f }
toString { "%(_e)+%(_f)" }
== (other) { (other is Union) && _e == other.e && _f == other.f }
}
class Concat is RE {
construct new(e, f) {
_e = e
_f = f
}
e { _e }
f { _f }
toString { "(%(_e))(%(_f))" }
== (other) { (other is Concat) && _e == other.e && _f == other.f }
}
class Star is RE {
construct new(e) { _e = e }
e { _e }
toString { "(%(_e))*" }
== (other) { (other is Star) && _e == other.e }
}
var simpleRE = Fn.new { |e|
var simple // recursive
simple = Fn.new { |e|
if (e is Union) {
var ee = simple.call(e.e)
var ef = simple.call(e.f)
if (ee == ef) {
return ee
} else if (ee is Union) {
return simple.call(Union.new(ee.e, Union.new(ee.f, ef)))
} else if (ee == empty) {
return ef
} else if (ef == empty) {
return ee
} else {
return Union.new(ee, ef)
}
} else if (e is Concat) {
var ee = simple.call(e.e)
var ef = simple.call(e.f)
if (ee == epsilon) {
return ef
} else if (ef == epsilon) {
return ee
} else if (ee == empty || ef == empty) {
return empty
} else if (ee is Concat) {
return simple.call(Concat.new(ee.e, Concat.new(ee.f, ef)))
} else {
return Concat.new(ee, ef)
}
} else if (e is Star) {
var ee = simple.call(e.e)
if ((ee is Empty) || (ee is Epsilon)) {
return epsilon
} else {
return Star.new(ee)
}
} else {
return e
}
}
var prevE = null
while (e != prevE) {
prevE = e
e = simple.call(e)
}
return e
}
var brzozowski = Fn.new { |a, b|
var m = a.count
for (n in m-1..0) {
var ann = a[n][n]
b[n] = Concat.new(Star.new(ann), b[n])
for (j in 0...n) a[n][j] = Concat.new(Star.new(ann), a[n][j])
for (i in 0...n) {
b[i] = Union.new(b[i], Concat.new(a[i][n], b[n]))
for (j in 0...n) {
a[i][j] = Union.new(a[i][j], Concat.new(a[i][n], a[n][j]))
}
}
for (i in 0...n) a[i][n] = empty
}
return b[0]
}
var a = [
[empty, Car.new("a"), Car.new("b")],
[Car.new("b"), empty, Car.new("a")],
[Car.new("a"), Car.new("b"), empty]
]
var b = [epsilon, empty, empty]
var re = brzozowski.call(a, b)
System.print(re)
System.print("\nwhich simplifies to:\n")
System.print(simpleRE.call(re))
- Output:
((0+(b)(((0)*)(a))+(a+(b)(((0)*)(b)))(((0+(a)(((0)*)(b)))*)(b+(a)(((0)*)(a)))))*)(1+(b)(((0)*)(0))+(a+(b)(((0)*)(b)))(((0+(a)(((0)*)(b)))*)(0+(a)(((0)*)(0))))) which simplifies to: ((b)(a)+(a+(b)(b))((((a)(b))*)(b+(a)(a))))*
Zig
The main difference from the C++ solution is that this Zig solution uses a memory pool whereas C++ uses shared pointers.
This Zig solution does not deallocate individual items created from the pool, it just eradicates the entire pool with a deferred pool.deinit(). Implementing deallocation for unused items individually would reduce maintainability and readability. Vergiß es.
const std = @import("std");
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
//
var pool = RegularExpressionPool.init(std.heap.page_allocator);
defer _ = pool.deinit();
//
// Define the NFA transition matrix a
const array = try allocator.alloc(*RegularExpression, 9);
defer allocator.free(array);
var a = try allocator.alloc([]*RegularExpression, 3);
defer allocator.free(a);
for (0..3) |i| a[i] = array[i * 3 .. i * 3 + 3]; // define row slices
a[0][0] = try EmptyExpr.init(&pool);
a[0][1] = try CarExpr.init(&pool, 'a');
a[0][2] = try CarExpr.init(&pool, 'b');
a[1][0] = try CarExpr.init(&pool, 'b');
a[1][1] = try EmptyExpr.init(&pool);
a[1][2] = try CarExpr.init(&pool, 'a');
a[2][0] = try CarExpr.init(&pool, 'a');
a[2][1] = try CarExpr.init(&pool, 'b');
a[2][2] = try EmptyExpr.init(&pool);
// Define the initial state vector b
const b = try allocator.alloc(*RegularExpression, 3);
defer allocator.free(b);
b[0] = try EpsilonExpr.init(&pool);
b[1] = try EmptyExpr.init(&pool);
b[2] = try EmptyExpr.init(&pool);
//
const writer = std.io.getStdOut().writer();
// Apply Brzozowski's algorithm
const dfa_expr = try brzozowski(&pool, a, b);
// Print the regular expression
try writer.print("{}\n\n", .{dfa_expr});
// Apply recursive simplification
const simplified_expr = try recursiveSimplify(&pool, dfa_expr, 0);
try writer.print("{}\n", .{simplified_expr});
}
fn brzozowski(pool: *RegularExpressionPool, a_: [][]*RegularExpression, b_: []*RegularExpression) !*RegularExpression {
const a = a_;
var b = b_;
var n = a_.len;
while (n != 0) {
n -= 1;
b[n] = try ConcatExpr.init(pool, try StarExpr.init(pool, a[n][n]), b[n]);
for (0..n) |j|
a[n][j] = try ConcatExpr.init(pool, try StarExpr.init(pool, a[n][n]), a[n][j]);
for (0..n) |i| {
b[i] = try UnionExpr.init(pool, b[i], try ConcatExpr.init(pool, a[i][n], b[n]));
for (0..n) |j|
a[i][j] = try UnionExpr.init(pool, a[i][j], try ConcatExpr.init(pool, a[i][n], a[n][j]));
}
for (0..n) |i|
a[i][n] = try EmptyExpr.init(pool);
}
return b[0];
}
fn recursiveSimplify(pool: *RegularExpressionPool, expr: *RegularExpression, depth: usize) !*RegularExpression {
if (depth > 200)
return expr
else {
const simplified = try expr.simplify(pool);
if (simplified.eql(expr))
return simplified
else
return recursiveSimplify(pool, simplified, depth + 1);
}
}
const RegularExpressionType = enum {
empty,
car,
epsilon,
@"union",
concat,
star,
};
const RegularExpressionPool = std.heap.MemoryPoolExtra(RegularExpression, .{});
const RegularExpression = union(RegularExpressionType) {
const Self = @This();
empty: EmptyExpr,
car: CarExpr,
epsilon: EpsilonExpr,
@"union": UnionExpr, // union is a keyword, @"union" is ok
concat: ConcatExpr,
star: StarExpr,
fn eql(self: *const Self, other: *const Self) bool {
// note: .@"union" is commutative
switch (self.*) {
inline else => |re| return re.eql(other),
}
}
fn simplify(self: *Self, pool: *RegularExpressionPool) error{OutOfMemory}!*Self {
switch (self.*) {
.empty, .car, .epsilon => return self,
inline else => |*re| return re.simplify(pool),
}
}
// refer to std.format.format documentation
pub fn format(self: *const Self, comptime _: []const u8, _: std.fmt.FormatOptions, writer: anytype) !void {
switch (self.*) {
inline else => |re| try re.write(writer),
}
}
fn getFieldName(comptime T: type) []const u8 {
inline for (@typeInfo(Self).@"union".fields) |field|
if (field.type == T)
return field.name;
unreachable;
}
};
const EmptyExpr = struct {
fn init(pool: *RegularExpressionPool) !*RegularExpression {
const self = try pool.create();
self.* = .{ .empty = .{} };
return self;
}
fn eql(_: *const EmptyExpr, other: *const RegularExpression) bool {
return switch (other.*) {
.empty => true,
else => false,
};
}
fn write(_: *const EmptyExpr, writer: anytype) !void {
try writer.writeByte('0');
}
};
const EpsilonExpr = struct {
fn init(pool: *RegularExpressionPool) !*RegularExpression {
const self = try pool.create();
self.* = .{ .epsilon = .{} };
return self;
}
fn eql(_: *const EpsilonExpr, other: *const RegularExpression) bool {
return switch (other.*) {
.epsilon => true,
else => false,
};
}
fn write(_: *const EpsilonExpr, writer: anytype) !void {
try writer.writeByte('1');
}
};
const CarExpr = struct {
c: u8,
fn init(pool: *RegularExpressionPool, c: u8) !*RegularExpression {
const self = try pool.create();
self.* = .{ .car = .{ .c = c } };
return self;
}
fn eql(self: *const CarExpr, other: *const RegularExpression) bool {
return switch (other.*) {
.car => |car| self.c == car.c,
else => false,
};
}
fn write(self: *const CarExpr, writer: anytype) !void {
try writer.writeByte(self.c);
}
};
const UnionExpr = struct {
e: *RegularExpression,
f: *RegularExpression,
fn init(pool: *RegularExpressionPool, e: *RegularExpression, f: *RegularExpression) !*RegularExpression {
const self = try pool.create();
self.* = .{ .@"union" = .{ .e = e, .f = f } };
return self;
}
fn eql(s: *const UnionExpr, other: *const RegularExpression) bool {
switch (other.*) {
.@"union" => |o| {
// Since Union is commutative, check both orders
return (s.e.eql(o.e) and s.f.eql(o.f)) or (s.e.eql(o.f) and s.f.eql(o.e));
},
else => return false,
}
}
fn simplify(self: *UnionExpr, pool: *RegularExpressionPool) !*RegularExpression {
const e = try self.e.simplify(pool);
const f = try self.f.simplify(pool);
if (e.eql(f))
return e;
switch (e.*) {
.empty => return f,
else => {},
}
switch (f.*) {
.empty => return e,
else => {},
}
// // new struct, pool allocation,
// return UnionExpr.init(pool, e, f);
// reuse struct, no pool allocation
self.* = .{ .e = e, .f = f };
const name = comptime RegularExpression.getFieldName(@TypeOf(self.*));
return @fieldParentPtr(name, self);
}
fn write(self: *const UnionExpr, writer: anytype) !void {
try writer.print("{}+{}", .{ self.e, self.f });
}
};
const ConcatExpr = struct {
e: *RegularExpression,
f: *RegularExpression,
fn init(pool: *RegularExpressionPool, e: *RegularExpression, f: *RegularExpression) !*RegularExpression {
const self = try pool.create();
self.* = .{ .concat = .{ .e = e, .f = f } };
return self;
}
fn eql(s: *const ConcatExpr, other: *const RegularExpression) bool {
return switch (other.*) {
.concat => |o| s.e.eql(o.e) and s.f.eql(o.f),
else => false,
};
}
fn simplify(self: *ConcatExpr, pool: *RegularExpressionPool) !*RegularExpression {
const e = try self.e.simplify(pool);
const f = try self.f.simplify(pool);
switch (e.*) {
.epsilon => return f,
else => {},
}
switch (f.*) {
.empty => return EmptyExpr.init(pool),
.epsilon => return e,
else => {},
}
switch (f.*) {
.empty => return EmptyExpr.init(pool),
else => {},
}
// // new struct, pool allocation,
// return ConcatExpr.init(pool, e, f);
// reuse struct, no pool allocation
self.* = .{ .e = e, .f = f };
const name = comptime RegularExpression.getFieldName(@TypeOf(self.*));
return @fieldParentPtr(name, self);
}
fn write(self: *const ConcatExpr, writer: anytype) !void {
try writer.print("({})({})", .{ self.e, self.f });
}
};
const StarExpr = struct {
e: *RegularExpression,
fn init(pool: *RegularExpressionPool, e: *RegularExpression) !*RegularExpression {
const self = try pool.create();
self.* = .{ .star = .{ .e = e } };
return self;
}
fn eql(s: *const StarExpr, other: *const RegularExpression) bool {
return switch (other.*) {
.star => |o| s.e.eql(o.e),
else => false,
};
}
fn simplify(self: *StarExpr, pool: *RegularExpressionPool) !*RegularExpression {
const e = try self.e.simplify(pool);
switch (e.*) {
.empty => return EpsilonExpr.init(pool),
.epsilon => return e,
else => {},
}
// // new struct, pool allocation,
// return StarExpr.init(pool, e);
// reuse struct, no pool allocation
self.* = .{ .e = e };
const name = comptime RegularExpression.getFieldName(@TypeOf(self.*));
return @fieldParentPtr(name, self);
}
fn write(self: *const StarExpr, writer: anytype) !void {
try writer.print("({})*", .{self.e});
}
};