Yes and no. The theoretical "regular expressions" are indeed Type-3 grammars in Chomsky's hierarchy. In practice, the common "RegEx" implementation implement a

Yes and no. The theoretical "regular expressions" are indeed Type-3 grammars in Chomsky's hierarchy. In practice, the common "RegEx" implementation implement a lot of extras, that break the theoretical backing, and also exhibit highly non-linear behaviors. Cf. this excellent paper by Russ Cox: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html