If you want to build a stateless system with transitions, you are limited to regular expressions (finite automata).

I don't think you'd like to write real-life applications using a regular language. It might be interesting as an experiment, but life without recursion or potentially infinite loops sounds bleak... Just imagine the struggle of creating some generic containers like trees / hash-tables.

I don't think it's impossible, and may be even interesting to see how far one can take such a language to make it useful, but enjoyable this is not...