A formal language is a set of words in some alphabet. It may be defined as being generated by a formal grammar or as being recognized by an automaton. For a regular language, it can also be described by a regular expression.
- A regular expression is not an automaton. I wonder if it is considered as a formal grammar?
- Do other non-regular languages, such as context-free languages and recursively enumerable languages, have counterparts of regular expressions?
Thanks and regards!
Firstly, I would like to point out that regular expressions are equivalent to finite state machines. Secondly, I would certainly say that regular expressions are (at least have a way to transform into) formal grammars. Regular languages are a subset of context-free languages, which are a subset of context-sensitive grammars. Wikipedia's description of a formal grammar certainly fits with one of the usual notations for context-free languages. Also, to systematically transform a regular expression into a formal grammar, take $a$ as any plain character in the following transformation:
$$T(PQ) = S_m \rightarrow T(P)\hbox{ ending at state }n - 1, S_n \rightarrow T(Q)$$ $$T(P|Q) = S_n \rightarrow T(P), S_n \rightarrow T(Q)$$ $$T(P^*) = S_n \rightarrow \epsilon, S_n \rightarrow T(PP^*)$$
Due to the fact that there have been many extensions to regular expressions, such as backreferences, and these cover a larger class of grammars, I would assume so. However, for those classes specifically, I don't know whether there are other regular expression like ways of representing them.