The main cause of this is Thomson’s construction leads to a lot of ε… We can do better. It’s somewhat difficult to follow the edges around this graph since we sometimes have more than one option of where to move right now. So, the input string does not match the regular expression. Then, we’re stuck – we have input left on the stack, but no way to process it. Finally, we move to state 4 on the first c. So, we move to state 1 on an ε, move to 3 on a b, then do a loop on 3 with the second b. We can’t move to state 1, since we won’t be able to process our first character a. You start at state 0 (the one with no input edges). Let’s try processing abbcc with this automaton.
$ fstdraw -acceptor -isymbols =ascii.syms regex.fst | dot -Tpng > regex.png $ fstcompile -acceptor -isymbols =ascii.syms > regex.fst
#REGULAR EXPRESSION FROM FINITE STATE AUTOMATA CODE#
Note: ε is the code for ε, the empty string. So, we end up with the following slightly reduced automaton: To represent this expression with a finite state automaton, we’ll use Thomson’s construction algorithm. For example, a*b+c? matches bc, but not abbcc. I will assume you’re familiar with the syntax and meaning. This is not meant to be a guide to regular expressions. How? Let’s start with regular expressions.
The figures in this post are made with OpenFST, an open source tool built by Google and NYU to manipulate finite state transducers (the older sibling of finite state automata).įinite state automata can be used to process regular expressions, do natural language processing, speech recognition, and more. A final state is usually indicated by the node having a double wall. Some edges consume ε (epsilon), the empty string.
You move between states (or nodes) in the automaton by consuming input. The input is accepted if, when you are finished reading all input, you are at a final state in the automaton. The input is either accepted or rejected. A finite state automaton is a graph with nodes and edges that can process input.
0 kommentar(er)
