# US 12,762,344 B2 · Splitting regular expressions between non-deterministic finite automaton and deterministic finite automaton > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,762,344 B2 - Document ID: US12762344B2 - Status: Granted - Kind: B2 - Application number: 18/661,796 - Filed: 2024-05-13 - Published: 2025-11-13 - Granted: 2026-10-13 - Earliest claimed: 2024-05-13 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Renat Idrisov - Web page: https://patentgrep.com/patent/US12762344B2 ## CPC - G06F 40/289: Phrasal analysis, e.g. finite state techniques or chunking - G06F 40/284: Lexical analysis, e.g. tokenisation or collocates - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems, methods, and computer-readable medium for splitting regular expressions between non-deterministic finite automaton and deterministic finite automaton are provided. A method includes parsing a set of regular expression patterns to generate an output. The method further includes processing the output to determine whether any of the set of regular expression patterns meets a specified criteria including whether a regular expression pattern is a single path regular expression. The method further includes using a first splitting process, splitting any of the set of regular expression patterns that meet the specified criteria into a first set of tokens. The method further includes using a second splitting process, different from the first splitting process, splitting any of the set of regular expression patterns that fail to meet the specified criteria into a second set of tokens. ## Claims ### Claim 1 A computer-implemented method comprising: parsing a set of regular expression patterns to generate an output; processing the output to determine whether any of the set of regular expression patterns meets a specified criteria including whether a regular expression pattern is a single path regular expression; using a first splitting process, splitting any of the set of regular expression patterns that meet the specified criteria into a first set of tokens; and using a second splitting process, different from the first splitting process, splitting any of the set of regular expression patterns that fail to meet the specified criteria into a second set of tokens, wherein the first splitting process outputs a first deterministic finite automaton (DFA) part of an abstract syntax tree (AST) and a first non-deterministic finite automaton (NFA) part of the AST, and wherein the second splitting process outputs a second DFA part of the AST and a second NFA part of the AST. ### Claim 2 (depends on 1) The method of claim 1, wherein the first splitting process comprises finding each of any prefixes that corresponds to a shortest unique prefix for any of the set of regular expression patterns that meet the specified criteria. ### Claim 3 (depends on 2) The method of claim 2, wherein the shortest unique prefix comprises a minimal prefix length that is unique against a prefix tree for any of the set of regular expression patterns that meet the specified criteria. ### Claim 4 (depends on 3) The method of claim 3, wherein any prefixes found to be corresponding to the shortest unique prefix are compiled for processing by a deterministic finite automaton. ### Claim 5 (depends on 4) The method of claim 4, wherein any remaining suffixes for the set of patterns, excluding any prefixes found to be corresponding to the shortest unique prefix, are compiled for processing by a non-deterministic finite automaton. ### Claim 6 (depends on 1) The method of claim 1, wherein the second splitting process comprises: (1) starting from each top level token of a regular expression calculating a size of a set of acceptable strings limited by a value of a specified minimal prefix length, (2) while keeping the size of the set of acceptable strings limited, increasing lengths of each of the acceptable strings, and (3) from among resulting sets of acceptable strings, selecting a first one of the acceptable strings that has a specified maximal length. ### Claim 7 (depends on 1) The method of claim 1, further comprising processing each of the first DFA part of the AST, the second DFA part of the AST, the first NFA part of the AST, and the second NFA part of the AST to generate output binary for storage. ### Claim 8 A computer-implemented method comprising: generating an abstract syntax tree by parsing a set of regular expression patterns; processing the abstract syntax tree to determine whether any of the set of regular expression patterns meets a specified criteria including: (1) whether a regular expression pattern is a single path regular expression, and (2) whether the regular expression pattern excludes assertions; using a first splitting process, splitting any of the set of regular expression patterns that meet the specified criteria into a first set of tokens; and using a second splitting process, different from the first splitting process, splitting any of the set of regular expression patterns that fail to meet the specified criteria into a second set of tokens, wherein the first splitting process outputs a first deterministic finite automaton (DFA) part of an abstract syntax tree (AST) and a first non-deterministic finite automaton (NFA) part of the AST, and wherein the second splitting process outputs a second DFA part of the AST and a second NFA part of the AST. ### Claim 9 (depends on 8) The method of claim 8, wherein the first splitting process comprises finding each of any prefixes that corresponds to a shortest unique prefix for any of the set of regular expression patterns that meet the specified criteria. ### Claim 10 (depends on 9) The method of claim 9, wherein the shortest unique prefix comprises a minimal prefix length that is unique against a prefix tree for any of the set of regular expression patterns that meet the specified criteria. ### Claim 11 (depends on 10) The method of claim 10, wherein any prefixes found to be corresponding to the shortest unique prefix are compiled for processing by a deterministic finite automaton. ### Claim 12 (depends on 11) The method of claim 11, wherein any remaining suffixes for the set of patterns, excluding any prefixes found to be corresponding to the shortest unique prefix, are compiled for processing by a non-deterministic finite automaton. ### Claim 13 (depends on 8) The method of claim 8, wherein the second splitting process comprises: (1) starting from each top level token of a regular expression calculating a size of a set of acceptable strings limited by a value of a specified minimal prefix length, and (2) while keeping the size of the set of acceptable strings limited, increasing lengths of each of the acceptable strings, and (3) from among resulting sets of acceptable strings, selecting a first one that of the acceptable strings that has a specified maximal length. ### Claim 14 (depends on 8) The method of claim 8, further comprising processing each of the first DFA part of the AST, the second DFA part of the AST, the first NFA part of the AST, and the second NFA part of the AST to generate output binary for storage. ### Claim 15 A non-transitory computer-readable medium comprising code corresponding to a method, the method comprising: parsing a set of regular expression patterns to generate an output; processing the output to determine whether any of the set of regular expression patterns meets a specified criteria including whether a regular expression pattern is a single path regular expression; using a first splitting process, splitting any of the set of regular expression patterns that meet the specified criteria into a first set of tokens; and using a second splitting process, different from the first splitting process, splitting any of the set of regular expression patterns that fail to meet the specified criteria into a second set of tokens, wherein the first splitting process outputs a first deterministic finite automaton (DFA) part of an abstract syntax tree (AST) and a first non-deterministic finite automaton (NFA) part of the AST, and wherein the second splitting process outputs a second DFA part of the AST and a second NFA part of the AST. ### Claim 16 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the first splitting process comprises finding each of any prefixes that corresponds to a shortest unique prefix for any of the set of regular expression patterns that meet the specified criteria. ### Claim 17 (depends on 16) The non-transitory computer-readable medium of claim 16, wherein the shortest unique prefix comprises a minimal prefix length that is unique against a prefix tree for any of the set of regular expression patterns that meet the specified criteria. ### Claim 18 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein any prefixes found to be corresponding to the shortest unique prefix are compiled for processing by a deterministic finite automaton. ### Claim 19 (depends on 18) The non-transitory computer-readable medium of claim 18, wherein any remaining suffixes for the set of patterns, excluding any prefixes found to be corresponding to the shortest unique prefix, are compiled for processing by a non-deterministic finite automaton. ### Claim 20 (depends on 15) The non-transitory computer-readable medium of claim 15, where the method further comprises processing each of the first DFA part of the AST, the second DFA part of the AST, the first NFA part of the AST, and the second NFA part of the AST to generate output binary for storage.