Relevant definition:

Pure signal: It is defined based on the following function:

$u$:$R\{absent,$present $\}$

At any time tinR, the input $u(t)$ is either absent$,$ meaning that there is no event at that time, or present, meaning that there is$.$ It carries no value, but instead provides all its information by being either present or absent at any given time.

If you encounter other unfamiliar definitions, please refer to the book or ask them through emails.

Problem $3.(25$ points$)$

Consider the deterministic finite$-$state machine in Figure $3\mathrm{.}14$ that models a simple traffic light.

inpt

out

Figure $3\mathrm{.}14$: Deterministic finite$-$state machine for Exercise $5$

$($a$)$ Formally write down the description of this FSM as a $5-$tuple:

$($States$,$ Inputs, Outputs, update, initialState$).$

$($b$)$ Give an execution trace of this FSM of length $4$ assuming the input tick is present on each reaction.

$($c$)$ Now consider merging the red and yellow states into a single stop state. Transitions that pointed into or out of those states are now directed into or out of the new stop state. Other transitions and the inputs and outputs stay the same. The new stop state is the new initial state. Is the resulting state machine deterministic? Why or why not? If it is deterministic, give a prefix of the trace of length $4.$ If it is non$-$deterministic, draw the computation tree up to depth $4.$