Hierarchical state machines in Simulink - Time & Space Complexity

Time Complexity: Hierarchical state machines

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a hierarchical state machine grows as the number of states increases.

How does adding more nested states affect the total steps the machine takes?

Scenario Under Consideration

Analyze the time complexity of the following Simulink hierarchical state machine snippet.

    % Simulink Stateflow Hierarchical State Machine Example
    chart = sfroot.find('-isa', 'Stateflow.Chart');
    stateA = chart.find('-isa', 'Stateflow.State', 'Name', 'StateA');
    subState1 = stateA.find('-isa', 'Stateflow.State', 'Name', 'SubState1');
    subState2 = stateA.find('-isa', 'Stateflow.State', 'Name', 'SubState2');
    
    % Transition from SubState1 to SubState2
    transition = stateA.find('-isa', 'Stateflow.Transition');
    if isempty(transition)
        transition = sfroot.create('Stateflow.Transition');
        transition.Source = subState1;
        transition.Destination = subState2;
    end
    

This code sets up a hierarchical state machine with a parent state and two nested substates, then creates a transition between the substates.

Identify Repeating Operations

Look for loops or repeated checks in the state machine execution.

• Primary operation: Checking active states and transitions during each step.
• How many times: Once per state per execution cycle, including nested states.

How Execution Grows With Input

As the number of states and nested levels grows, the machine checks more states and transitions each cycle.

Input Size (number of states)	Approx. Operations per cycle
10	About 10 state checks
100	About 100 state checks
1000	About 1000 state checks

Pattern observation: The number of operations grows roughly in direct proportion to the number of states.

Final Time Complexity

Time Complexity: O(n)

This means the time to process the state machine grows linearly with the number of states.

Common Mistake

[X] Wrong: "Adding nested states does not increase processing time much because they are inside other states."

[OK] Correct: Each nested state still needs to be checked every cycle, so more nested states add more work.

Interview Connect

Understanding how hierarchical state machines scale helps you design efficient models and explain your reasoning clearly in discussions.

Self-Check

"What if we added parallel states that run simultaneously? How would that affect the time complexity?"

Practice

1. What is the main purpose of using hierarchical state machines in Simulink Stateflow?

easy

A. To organize states inside bigger states for simpler system modeling

B. To speed up simulation by skipping states

C. To create random state transitions automatically

D. To remove all states and use only transitions

Solution

1. Step 1: Understand hierarchical state machines concept

   Hierarchical state machines group smaller states inside bigger parent states to manage complexity.

2. Step 2: Identify the main benefit in Simulink Stateflow

   This grouping helps model complex systems in smaller, manageable parts.

3. Final Answer:

   To organize states inside bigger states for simpler system modeling -> Option A

4. Quick Check:

   Hierarchical states simplify models = A [OK]

Hint: Think: bigger states hold smaller states inside [OK]

Common Mistakes:

• Confusing hierarchical states with speeding simulation
• Thinking transitions create states automatically
• Believing hierarchical states remove all states

2. Which of the following is the correct way to define a child state inside a parent state in Simulink Stateflow?

easy

A. Draw the child state box next to the parent state box without overlap

B. Use a transition arrow from parent to child state only

C. Place the child state box completely inside the parent state box

D. Name the child state with the same name as the parent state

Solution

1. Step 1: Recall how hierarchical states are shown visually

   Child states are drawn inside the parent state box to show containment.

2. Step 2: Identify correct visual representation

   Only placing the child state fully inside the parent state box correctly defines hierarchy.

3. Final Answer:

   Place the child state box completely inside the parent state box -> Option C

4. Quick Check:

   Child inside parent box = B [OK]

Hint: Child states go inside parent state box visually [OK]

Common Mistakes:

• Placing child states outside parent states
• Using transitions to define hierarchy instead of containment
• Naming child and parent states identically

3. Consider this Stateflow snippet: A parent state P has two child states S1 and S2. If the machine starts in P and the default child state is S1, what is the active state after initialization?

medium

A. S2 only

B. S1 only

C. P only

D. P and S1

Solution

1. Step 1: Understand hierarchical state activation

   When a parent state is active, its default child state is also active.

2. Step 2: Apply to given states

   Starting in parent P activates P and its default child S1.

3. Final Answer:

   P and S1 -> Option D

4. Quick Check:

   Parent and default child active = A [OK]

Hint: Parent and default child states are active together [OK]

Common Mistakes:

• Thinking only parent or only child is active
• Confusing default child with other child
• Ignoring hierarchical activation rules

4. You have a hierarchical state machine where a child state C is not activating when the parent state P is active. What is the most likely cause?

medium

A. The child state C is not placed inside the parent state P

B. The parent state P has no exit transitions

C. The child state C has no transitions

D. The parent state P is not connected to any other state

Solution

1. Step 1: Check child state placement in hierarchy

   For a child state to activate with its parent, it must be inside the parent's boundary.

2. Step 2: Identify cause of non-activation

   If C is outside P, it won't activate when P is active.

3. Final Answer:

   The child state C is not placed inside the parent state P -> Option A

4. Quick Check:

   Child outside parent means no activation = C [OK]

Hint: Check if child state is inside parent state box [OK]

Common Mistakes:

• Assuming transitions affect child activation directly
• Ignoring visual containment rules
• Confusing exit transitions with activation

5. You want to model a traffic light system with hierarchical states: a parent state Operational and child states Green, Yellow, and Red. How can hierarchical states help improve this model?

hard

A. By using hierarchical states to skip the yellow light automatically

B. By grouping the light colors inside Operational, you can manage transitions and timers centrally

C. By creating separate machines for each light color without hierarchy

D. By removing the parent state and using only child states for simplicity

Solution

1. Step 1: Understand hierarchical grouping benefits

   Grouping child states inside a parent allows shared logic like timers or transitions at the parent level.

2. Step 2: Apply to traffic light example

   Parent Operational can handle common behavior, while child states represent light colors.

3. Final Answer:

   By grouping the light colors inside Operational, you can manage transitions and timers centrally -> Option B

4. Quick Check:

   Hierarchy centralizes shared logic = D [OK]

Hint: Use parent state for shared logic, children for specific states [OK]

Common Mistakes:

• Removing parent state loses shared control
• Using separate machines complicates coordination
• Assuming hierarchy skips states automatically