Skip to content

Deterministic Finite-State Automata Library for Rust, written in L1

License

Notifications You must be signed in to change notification settings

andrew-johnson-4/L1DFA

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

62 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

L1 DFA

Deterministic Finite-State Automata Library for Rust, written in L1.

Features

  • try_parse(regex)
    • space complexity = $O(2^x)$
    • time complexity = $O(2^x)$
    • worst case example: /(01|10)*[01]{x}/
  • x.accepts(s)
    • time complexity = $s$
  • x.is_empty()
    • time complexity = $x$
  • x.complement()
    • space complexity = $x$
    • time complexity = $x$
  • x.intersect(y)
    • space complexity = $xy$
    • time complexity = $xy$
  • x.union(y)
    • space complexity = $xy$
    • time complexity = $xy$
  • x.minimize()
    • time complexity = $x\log x\Sigma_x$
  • x.is_subset_of(y)
    • space complexity = $xy$
    • time complexity = $xy$
  • x.reverse()
    • space complexity = $O(2^x)$
    • time complexity = $O(2^x)$
    • worst case example: /[01]{x}(01|10)*/

Releases

No releases published

Sponsor this project

 

Packages

No packages published

Languages