Managed to do this challenge. The way the code works is to make a table of equations describing the FSM to match the numbers, and then algebraically reduces it down to a single term. The regexes it produces are longer than they need to be but they work. Simple solution but took a lot of thinking to get there.

Here it is in action for n = 5:

0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 4(0) 4 = 2(0) | 4(1) 0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 4(1*0) 4 = 2(0) 0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 2(01*0) 0 = 0(0) | 2(1) 1 = 0(1) | 3(0) 2 = 1(0) | 3(1) 3 = 1(1) | 2(01*0) 0 = 0(0) | 2(1) 1 = 0(1) | 1(10) | 2(01*00) 2 = 1((0|11)) | 2(01*01) 0 = 0(0) | 2((01*01)*1) 1 = 0(1) | 2((01*01)*01*00) 2 = 1((10)*(0|11)) 0 = 0(0) | 1((10)*(0|11)(01*01)*1) 1 = 0(1) | 1((10)*(0|11)(01*01)*01*00) 0 = 0(0) | 1(((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1) 1 = 0(1) 0 = 0((0|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)) regex: ^(0|1((10)*(0|11)(01*01)*01*00)*(10)*(0|11)(01*01)*1)+$

Code here: https://pastebin.com/ys9MeW5T