Hierarchical state machine concept in Embedded C - Step-by-Step Execution

Concept Flow - Hierarchical state machine concept

Start

↓

Top State

↓

Substate A

↓

Sub-substate A1

↓

Sub-substate A2

↓

Substate B

↓

Sub-substate B1

↓

Sub-substate B2

↓

Event Occurs

↓

Check Transitions

↓

Change State Hierarchically

↓

Execute Entry/Exit Actions

↓

Wait for Next Event

The hierarchical state machine starts at a top state, which contains nested substates. When an event occurs, transitions are checked from the current substate up through parent states, changing states and running entry/exit actions accordingly.

Execution Sample

Embedded C

typedef enum {TOP, A, A1, A2, B, B1, B2} State;
State current_state = TOP;

void event_handler(Event e) {
  switch(current_state) {
    case A1: if(e == EVT_X) current_state = B1; break;
  }
}

This code shows a simple hierarchical state machine with states and a transition from substate A1 to B1 on event EVT_X.

Execution Table

Step	Current State	Event	Transition Condition	New State	Entry/Exit Actions
1	TOP	None	No event	TOP	None
2	TOP	Init	Enter initial substate A	A	Enter A
3	A	Init	Enter initial sub-substate A1	A1	Enter A1
4	A1	EVT_X	If EVT_X in A1, go to B1	B1	Exit A1, Exit A, Enter B, Enter B1
5	B1	None	No event	B1	None
6	B1	EVT_Y	No transition	B1	None
7	B1	EVT_Z	Transition to B2	B2	Exit B1, Enter B2
8	B2	None	No event	B2	None
9	B2	EVT_STOP	Transition to TOP	TOP	Exit B2, Exit B, Enter TOP
10	TOP	None	No event	TOP	None

💡 Execution stops when no more events or transitions occur.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 7	After Step 9	Final
current_state	TOP	A	A1	B1	B2	TOP	TOP

Key Moments - 3 Insights

Why do we exit both A1 and A when transitioning from A1 to B1?

Because B1 is under B, a different branch from A, we must exit the current substate A1 and its parent A before entering B and B1, as shown in step 4 of the execution_table.

What happens if an event has no matching transition in the current state?

The state machine stays in the current state without changes or actions, as seen in step 6 where EVT_Y does not cause a transition from B1.

How does the machine know which substate to enter initially?

On entering a parent state, the machine enters its initial substate automatically, like entering A then A1 in steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current_state after step 4?

A B1

B A1

C A

D TOP

💡 Hint

Check the 'New State' column at step 4 in the execution_table.

At which step does the state machine exit state B1?

A Step 6

B Step 9

C Step 7

D Step 4

💡 Hint

Look for 'Exit B1' in the Entry/Exit Actions column in the execution_table.

If the event EVT_X did not cause a transition in A1, what would happen to current_state after step 4?

A It would change to B1 anyway

B It would remain A1

C It would change to TOP

D It would change to A

💡 Hint

Refer to the key_moments about no matching transition and step 6 where no transition keeps the state unchanged.

Concept Snapshot

Hierarchical State Machine (HSM):
- States can contain nested substates.
- Events trigger transitions checked from current substate up.
- Exiting a state exits all nested substates.
- Entering a state enters its initial substate.
- Entry/Exit actions run on state changes.

Full Transcript

A hierarchical state machine organizes states in a tree structure with parent and nested substates. The machine starts at a top state and enters initial substates automatically. When an event occurs, it checks for transitions starting from the current substate up through parent states. If a transition is found, it exits the current substate and any parent states not shared with the target, then enters the target state and its initial substates, running entry and exit actions accordingly. If no transition matches, the state remains unchanged. This structure helps manage complex behaviors by grouping related states and transitions.

Practice

1. What is the main benefit of using a hierarchical state machine in embedded C programming?

easy

A. It removes the need for any state transitions.

B. It eliminates the need for events to change states.

C. It allows states to run in parallel without interaction.

D. It organizes states into groups, making complex behavior easier to manage.

Solution

1. Step 1: Understand hierarchical state machine purpose

   Hierarchical state machines group related states inside bigger states to simplify complex logic.

2. Step 2: Identify the benefit

   This grouping helps share common actions and manage transitions more clearly.

3. Final Answer:

   It organizes states into groups, making complex behavior easier to manage. -> Option D

4. Quick Check:

   Grouping states = easier management [OK]

Hint: Think of states like folders inside folders for clarity [OK]

Common Mistakes:

• Thinking events are not needed in hierarchical state machines
• Believing states run independently without interaction
• Assuming no transitions are required

2. Which of the following is the correct way to define a sub-state inside a parent state in embedded C code for a hierarchical state machine?

easy

A. typedef enum { STATE_PARENT, STATE_CHILD } State;

B. typedef enum { STATE_PARENT, STATE_CHILD } State; // with STATE_CHILD as a separate enum

C. typedef enum { STATE_PARENT, STATE_CHILD } State; // with STATE_CHILD nested inside STATE_PARENT logically

D. typedef enum { STATE_PARENT, STATE_CHILD } State; // with STATE_CHILD declared inside STATE_PARENT block

Solution

1. Step 1: Understand enum usage for states

   In embedded C, states are often defined as enums. Logical nesting is done by naming and design, not by code nesting.

2. Step 2: Identify correct sub-state definition

   typedef enum { STATE_PARENT, STATE_CHILD } State; // with STATE_CHILD nested inside STATE_PARENT logically correctly states that STATE_CHILD is logically nested inside STATE_PARENT, even though enums are flat.

3. Final Answer:

   typedef enum { STATE_PARENT, STATE_CHILD } State; // with STATE_CHILD nested inside STATE_PARENT logically -> Option C

4. Quick Check:

   Logical nesting, not code nesting [OK]

Hint: Enums are flat; nesting is logical, not syntax [OK]

Common Mistakes:

• Trying to nest enums inside enums (not allowed in C)
• Assuming code blocks define sub-states
• Declaring sub-states as separate enums without relation

3. Given the following code snippet for a hierarchical state machine, what will be the output when event EVENT_START occurs in STATE_IDLE?

#define EVENT_START 1
typedef enum { STATE_IDLE, STATE_ACTIVE, STATE_ACTIVE_SUB } State;
State current_state = STATE_IDLE;

void handle_event(int event) {
  switch (current_state) {
    case STATE_IDLE:
      if (event == EVENT_START) {
        current_state = STATE_ACTIVE;
        printf("Entered ACTIVE state\n");
      }
      break;
    case STATE_ACTIVE:
      if (event == EVENT_START) {
        current_state = STATE_ACTIVE_SUB;
        printf("Entered ACTIVE_SUB state\n");
      }
      break;
    default:
      printf("No action\n");
  }
}

handle_event(EVENT_START);

medium

A. No action

B. Entered ACTIVE state

C. Entered ACTIVE_SUB state

D. Compilation error

Solution

1. Step 1: Check initial state and event

   The current_state is STATE_IDLE. The event is EVENT_START.

2. Step 2: Follow switch-case logic for STATE_IDLE

   On EVENT_START in STATE_IDLE, current_state changes to STATE_ACTIVE and prints "Entered ACTIVE state".

3. Final Answer:

   Entered ACTIVE state -> Option B

4. Quick Check:

   STATE_IDLE + EVENT_START = Entered ACTIVE state [OK]

Hint: Trace current state before event handling [OK]

Common Mistakes:

• Assuming it jumps directly to sub-state
• Ignoring initial state value
• Confusing event handling in different states

4. Identify the error in this hierarchical state machine event handler code snippet:

#define EVENT_GO 1
typedef enum { STATE_TOP, STATE_SUB } State;
State current_state = STATE_TOP;

void handle_event(int event) {
  switch (current_state) {
    case STATE_TOP:
      if (event = EVENT_GO) {
        current_state = STATE_SUB;
        printf("Moved to SUB state\n");
      }
      break;
    case STATE_SUB:
      printf("In SUB state\n");
      break;
  }
}

medium

A. Using assignment (=) instead of comparison (==) in if condition

B. Missing default case in switch statement

C. Incorrect enum values for states

D. No return statement in function

Solution

1. Step 1: Examine if condition in STATE_TOP case

   The condition uses single '=' which assigns EVENT_GO to event instead of comparing.

2. Step 2: Understand impact of assignment in if

   This causes the condition to always be true if EVENT_GO is non-zero, leading to unintended behavior.

3. Final Answer:

   Using assignment (=) instead of comparison (==) in if condition -> Option A

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Check if conditions for == vs = errors [OK]

Common Mistakes:

• Confusing assignment and comparison operators
• Ignoring missing default case (not critical here)
• Expecting return in void function

5. You want to design a hierarchical state machine in embedded C where STATE_RUNNING has two sub-states: STATE_RUNNING_FAST and STATE_RUNNING_SLOW. Which approach correctly models this hierarchy and allows shared entry actions for STATE_RUNNING and specific actions for its sub-states?

hard

A. Define separate enums for all states and use nested switch-case to handle parent and sub-states with shared and specific actions.

B. Use a single enum with flat states and duplicate code for shared actions in each sub-state case.

C. Use multiple variables to track parent and sub-state separately without nesting logic.

D. Implement sub-states as independent states without any relation to the parent state.

Solution

1. Step 1: Understand hierarchical state machine design

   Parent states group sub-states to share common behavior and allow specific sub-state actions.

2. Step 2: Identify correct coding approach

   Defining separate enums for parent and sub-states and using nested switch-case allows shared entry actions for parent and specific actions for sub-states efficiently.

3. Final Answer:

   Define separate enums for all states and use nested switch-case to handle parent and sub-states with shared and specific actions. -> Option A

4. Quick Check:

   Nested switch-case models hierarchy best [OK]

Hint: Use nested switch-case for parent and sub-state actions [OK]

Common Mistakes:

• Duplicating shared actions in sub-states
• Tracking states separately without hierarchy
• Ignoring parent-child relationship in code