Can EEPROMs have feedback networks to make state machines?
Put a register in the feedback path and yes.
Common in the early 80s when TTL PROMs were cheaper than PALs (before FPGAs came along)
Use a clocked register rather than a latch, to hold the ROM output. This register holds the state which forms part of the next ROM address (and may hold outputs too). Then inputs form a further part of the ROM address, so the next state depends on the current state and the inputs. State changes can only happen on clock edges.
As seen in this article mentioned in a comment.