Finite State Machine validity
JavaScript (ES6), 81 bytes

s=&gt;(a=[...s]).map(_=&gt;a.map((m,i)=&gt;p=i%2&amp;r[s[i-1]]?r[m]=1:r[m]),r={},r[s[0]]=1)&amp;&amp;p


Explanation

Takes the states as a string and returns a 1 for true or undefined for false. This method was the shortest I could find, but it means that it's impossible to include the bonus because it just determines reachability, not the paths.

s=&gt;
  (a=[...s])        // a = states as an array
  .map(_=&gt;          // loop a number of times to ensure all states have been reached
    a.map((m,i)=&gt;   // for each state m at index i
      p=            // p = the reachability of the final state
        i%2         // if this is the last state of a pair
        &amp;r[s[i-1]]? // and the first state is reachable
          r[m]=1    // set the last state and p to reachable
          :r[m]     // else set p to the reachability of the state
    ),
    r={},           // map of truthy values for reachable states
    r[s[0]]=1       // set the initial state to reachable
  )
  &amp;&amp;p               // return the final result


Test



var solution = s=&gt;(a=[...s]).map(_=&gt;a.map((m,i)=&gt;p=i%2&amp;r[s[i-1]]?r[m]=1:r[m]),r={},r[s[0]]=1)&amp;&amp;p
&lt;input type="text" id="input" value="ABACADCDBCDEBE" /&gt;
&lt;button onclick="result.textContent=solution(input.value)"&gt;Go&lt;/button&gt;
&lt;pre id="result"&gt;&lt;/pre&gt;