Algorithm</h3>
<p>To extend our recognition algorithm to a parsing algorithm, we need to keep track of the paths taken through the automaton. Similar to recognition, we’ll define this recursively.</p>
<p>First, let’s define a path as a sequence of symbol-state pairs, where each pair represents a transition in the automaton. For a path <span class="math inline">\(p\)</span>, we denote the last state in the path as <span class="math inline">\(\text{last-state}(p)\)</span>.</p>
<p>We need a helper function