2-Tag System but it's in TypeScript type system (TypeScriptの型システムで2-タグシステムを動かす)

type Rule = {[_ in string]: string}

/*
R: Rules
L: STOP character
W: Word
Out: Output
*/
type TagSystemSteps<R extends Rule, L extends string, W extends string, Out extends string[]=[]> = 
  W extends `${infer F}${infer _}${infer Rest}`?
    F extends L ? 
      [...Out, W]
      : R[F] extends `${infer O}`?    
        TagSystemSteps<R, L, `${Rest}${O}`, [...Out, W]> 
        : unknown
    : [...Out, W]

type TagSystem<R extends Rule, L extends string, W extends string> = 
    [0, ...TagSystemSteps<R, L, W>][TagSystemSteps<R, L, W>["length"]]

Usage (使い方)

/*
* Rules:
*  A -> BH
*  B -> A
*  H -> *STOP*
*  
* Initial Word: ABB
* (ABB -> BBH -> HA)
*/

type TagSystemOut = TagSystem<{"A": "BH", "B":"A"}, "H", "ABB"> // "HA"

type TagSystemStepOut = TagSystemSteps<{"A": "BH", "B":"A"}, "H", "ABB"> // ["ABB", "BBH", "HA"]

/*
* Rules: Same
* 
* Initial Word: ABBB
* (ABBB -> BBBH -> BHA -> AA -> BH -> A)
*/
type TagSystemStepOut2 = TagSystemSteps<{"A": "BH", "B":"A"}, "H", "ABBB"> // ["ABBB", "BBBH", "BHA", "AA", "BH", "A"]

Playground