Pensando sobremeu outro problema, decidi que não posso nem criar uma expressão regular que corresponda a números romanos (sem falar em uma gramática sem contexto que os gerará)

O problema está correspondendo apenas a números romanos válidos. Por exemplo, 990 NÃO é "XM", é "CMXC"

Meu problema ao fazer a regex para isso é que, para permitir ou não certos caracteres, preciso olhar para trás. Vamos pegar milhares e centenas, por exemplo.

Eu posso permitir M {0,2} C? M (para permitir 900, 1000, 1900, 2000, 2900 e 3000). No entanto, se a correspondência estiver no CM, não posso permitir que os seguintes caracteres sejam C ou D (porque eu já tenho 900).

Como posso expressar isso em uma regex?
Se simplesmente não é expressável em uma regex, é expressável em uma gramática livre de contexto?