Converts NFAs (and DFAs) to a regular expressions using the state removal method.

nfa-to-regex: convert NFAs (and DFAs) to regular expressions

An implementation of the state removal technique for converting an NFA to a regular expression.

No optimization is done, so results may be surprising.

Examples

A Simple NFA

A simple example NFA:

nfa := New()
nfa.addEdge("1", "1", "a")
nfa.addEdge("1", "2", "b")
nfa.addEdge("2", "2", "c")
nfa.addEdge("2", "3", "d")
nfa.addEdge("3", "3", "e")
nfa.addEdge("3", "1", "x")
nfa.nodes["1"].isInitial = true
nfa.nodes["3"].isTerminal = true

Which produces the state diagram:

And the regular expression:

a*bc*d(e|xa*bc*d)*

Binary Multiples of 3

An NFA which matches multiples of 3:

func MakeNFAMultiplesOfN(n int) *NFA {
    str := func(i int) string { return strconv.Itoa((i)) }
    nfa := New()
    for i := 0; i < n; i += 1 {
        nfa.addEdge(str(i), str((i*2)%n), "0")
        nfa.addEdge(str(i), str((i*2+1)%n), "1")
    }
    nfa.addEdge("start", "0", "0")
    nfa.addEdge("start", "1", "1")
    nfa.nodes["start"].isInitial = true
    nfa.nodes["0"].isTerminal = true
    return nfa
}

Which produces the state diagram:

And the regular expression:

(0(0|11|10(1|00)*01)*|11(0|11|10(1|00)*01)*|10(1|00)*01(0|11|10(1|00)*01)*)

State Removal Steps

Given an NFA with multiple initial and terminal nodes:

nfa := New()
nfa.addEdge("1", "2", "a")
nfa.addEdge("2", "3", "b")
nfa.addEdge("2", "2", "l")
nfa.addEdge("4", "2", "x")
nfa.addEdge("2", "5", "y")
nfa.nodes["1"].isInitial = true
nfa.nodes["4"].isInitial = true
nfa.nodes["3"].isTerminal = true
nfa.nodes["5"].isTerminal = true

These are the steps used to convert it to a regular expression:

  1. Initial NFA:

  1. Creation of initial and terminal states:

  1. Removal of node 4:

  1. Removal of node 5:

  1. Removal of node 1:

  1. Removal of node 2:

  1. And finally, the removal of node 3:

Which yields the regular expression:

(xl*b|xl*y|al*b|al*y)
Similar Resources

checkip is a CLI tool and library that checks an IP address using various public services.

checkip is a CLI tool and library that checks an IP address using various public services.

checkip is a CLI tool and library that checks an IP address using various public services.

Dec 20, 2022

Get subdomain list and check whether they are active or not by each response code. Using API by c99.nl

Get subdomain list and check whether they are active or not by each response code. Using API by c99.nl

getsubdomain Get subdomain list and check whether they are active or not by each response code. Using API by c99.nl Installation ▶ go install github.c

Oct 24, 2022

Building microservice to list products of one ecommerce using golang and gRPC

Building microservice to list products of one ecommerce using golang and grpc Command for generate protobuf $ protoc -I ./protos/... file.proto --go_o

Mar 26, 2022

A web app written in Go, using Auth0 and deployed to Heroku

hundred-go This project demonstrates a web app written in Go that uses free Auth0 for authentication and authorization. Web Apps - Plan for Auth Early

Dec 22, 2021

Gogrok is a self hosted, easy to use alternative to ngrok. It uses SSH as a base protocol, using channels and existing functionality to tunnel requests to an endpoint.

gogrok A simple, easy to use ngrok alternative (self hosted!) The server and client can also be easily embedded into your applications, see the 'serve

Dec 3, 2022

A basic sample web-services application using Go and Gin.

Sample application for Go Web Services A very basic web-services application built with go-lang and the Gin Web Framework. Based on https://github.com

Jan 13, 2022

Hostkeydns - Library for verifying remote ssh keys using DNS and SSHFP resource records

hostkeydns import "suah.dev/hostkeydns" Package hostkeydns facilitates verifying

Feb 11, 2022

A library to simplify writing applications using TCP sockets to stream protobuff messages

BuffStreams Streaming Protocol Buffers messages over TCP in Golang What is BuffStreams? BuffStreams is a set of abstraction over TCPConns for streamin

Dec 13, 2022

Pure-Go library for cross-platform local peer discovery using UDP multicast :woman: :repeat: :woman:

Pure-Go library for cross-platform local peer discovery using UDP multicast :woman: :repeat: :woman:

peerdiscovery Pure-go library for cross-platform thread-safe local peer discovery using UDP multicast. I needed to use peer discovery for croc and eve

Jan 8, 2023
Comments
  • Would it be possible to add a canonical regex step or a simplify/unique step?

    Would it be possible to add a canonical regex step or a simplify/unique step?

    For example I am getting the following results:

    NFA: 
    ^gdt-[0-9A-Za-z]([0-9A-Za-z])*-s$(s$)*
    ^gdt-[0-9A-Za-z]([0-9A-Za-z])*-c$(s$)*
    ^gdt-[0-9A-Za-z]([0-9A-Za-z])*-s$(s$)*
    ^gdt-[0-9A-Za-z]([0-9A-Za-z])*-c$(s$)*
    

    NOTE: I replaced the | w/ newlines

    With the following graph

    Simplified (aka what I need):

    ^gdt-[0-9A-Za-z]+-c$
    ^gdt-[0-9A-Za-z]+-s$
    

    or unified

    '^gdt-[0-9A-Za-z]+-(c|s)$'
    

    Is that possible?

Related tags
Reads MAWS formatted data and converts it into JSON output stream.

maws2json Usage examples Over serial line (stdin pipe) Lets assume that Vaisala weather station is connected via RS232 to USB serial dongle in /dev/tt

Feb 6, 2022
Multi-Threaded PURGE Request Method Check Tool

purgex Multi-Threaded PURGE Request Method Check Tool REQUIREMENTS AND INSTALLATION Build purgex: git clone https://github.com/jayateertha043/purgex.g

Jan 18, 2022
A pluggable backend API that enforces the Event Sourcing Pattern for persisting & broadcasting application state changes
A pluggable backend API that enforces the Event Sourcing Pattern for persisting & broadcasting application state changes

A pluggable "Application State Gateway" that enforces the Event Sourcing Pattern for securely persisting & broadcasting application state changes

Nov 1, 2022
This service is intented to collect data using grpc using Go lang backend and cassandra DB as storage

Go Data Collection This service is intented to collect data using grpc using Go lang backend and cassandra DB as storage. Dev Setup make test_env make

Apr 13, 2022
httpx is a fast and multi-purpose HTTP toolkit allows to run multiple probers using retryablehttp library, it is designed to maintain the result reliability with increased threads.
httpx is a fast and multi-purpose HTTP toolkit allows to run multiple probers using retryablehttp library, it is designed to maintain the result reliability with increased threads.

Features • Installation • Usage • Running httpx • Notes • Join Discord httpx is a fast and multi-purpose HTTP toolkit allow to run multiple probers us

Jan 8, 2023
An experimental Tor-Proxy serivce written in Go using Go-proxy and Go-libtor.

tor-proxy An experimental standalone tor-proxy service built with Go, using go-proxy, go-libtor and bine. This is a simple replacement to Tor's origin

Nov 9, 2022
A toy MMO example built using Ebiten and WebRTC DataChannels (UDP)
A toy MMO example built using Ebiten and WebRTC DataChannels (UDP)

Ebiten WebRTC Toy MMO ⚠️ This is a piece of incomplete hobby work and not robust. Please read the "Why does this project exist?" section. What is this

Aug 28, 2022
sonarbyte is a simple and fast subdomain scanner written in go to extract subdomain from Rapid7's DNS Database using omnisint's api.
 sonarbyte is a simple and fast subdomain scanner written in go to extract subdomain from Rapid7's DNS Database using omnisint's api.

sonarbyte Description Sonarbyte is a simple and fast subdomain scanner written in go to extract subdomains from Rapid7's DNS Database using omnisint's

Jul 27, 2022
Backend implementation using go, proto3 and gRPC for a mock online store

Backend implementation using go, proto3 and gRPC for a mock online store Ricardo RICO URIBE Tasks I - Order service The current system exposes a produ

Oct 10, 2021
Native macOS networking for QEMU using vmnet.framework and socket networking.

qemu-vmnet Native macOS networking for QEMU using vmnet.framework and socket networking. Getting started TODO -netdev socket,id=net0,udp=:1234,localad

Jan 5, 2023