Problem 5. Invariant Doesn't Imply Reachable Consider the state machine that we define as follows: States are specified by strings consisting of the following three symbols: {[],S}. For example, some possible states include [, SSS, CSCS. The start state is the string S. Transitions are defined by replacing an S in a given string with either [S], []s, or [] [] For example, here is a valid sequence of transitions: S [S] [CS] (000) Note that this final string cannot have more transitions as it no longer contains an S. (a) Prove that "the string contains neither S[ nor SS as substrings" is an invariant of the state machine. (b) We say a string is balanced if it has the same number of ['s and ]'s and each [ matches a distinct corresponding ) that comes later in the string. For example, [[] [C]]) is a balanced string, but [[ ]] ( and (() are not balanced strings. Prove that "the string is balanced is an invariant of the state machine. (c) Consider the two strings S[C]) and ]]] [[C. Do they satisfy the invariant from part (a)? from part (b)? Is either of them reachable? (d) If a state satisfies both of the invariants, is it true then that the state must be reachable? Hint: Try coming up with a small counterexample to this claim and briefly justify why it is not reachable