HardNLPnlp-298

FST Composition State Count

Problem

Count the reachable states of the composition of two finite-state transducers. t1 and t2 are transition lists of [from_state, input_symbol, output_symbol, to_state], and composition connects a t1 transition to a t2 transition when t1's output symbol equals t2's input symbol.

Start from the state pair [start1, start2] and follow all matching transitions. Return the number of distinct state pairs reachable, including the start pair.

Hint

Depth-first search over pairs of transducer states, advancing only on matching middle symbols.

Test cases

case 1

in: [[[0,"a","x",1],[1,"b","y",2]],[[0,"x","p",1],[1,"y","q",2]],0,0]

expected: 3

case 2

in: [[[0,"a","x",1]],[[0,"x","p",1]],0,0]

expected: 2

case 3

in: [[[0,"a","z",1]],[[0,"x","p",1]],0,0]

expected: 1

case 4

in: [[],[[0,"x","p",1]],0,0]

expected: 1

case 5

in: [[[0,"a","x",1],[0,"a","y",2]],[[0,"x","p",0],[0,"y","q",1]],0,0]

expected: 3

Starter codePython

def fst_composition_state_count(t1, t2, start1, start2):
    # Your code here
    pass

5 test cases · run your code against them in the editor