Cucumber is not really a native DSL. The scenario files are simply text files that are parsed (pattern matched) by Cucumber, which is a parser that's written in Ruby. It could well be written in Python, too.
If you look at Steak (https://github.com/cavalle/steak), however, this is a real native Ruby DSL, and such a thing is impossible to ever do as elegant in Python.
Maybe, but my enthusiasm for DSLs in ruby has diminished a lot in the 6+ years I've been doing ruby work. DSLs don't compose well and it's usually easier to learn a new api than yet another new mini-language.
In contrast, however, I give you Cucumber scenario files. Yes, Given/When/Then are methods but it's still a very elegant DSL.
I'll do some poking into prolog and forth-based DSLs. You've peaked my interest.