# The way that a regular expression describes a regular language

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.

1. A regular expression is not an automaton. I wonder if it is considered as a formal grammar?
2. Do other non-regular languages, such as context-free languages and recursively enumerable languages, have counterparts of regular expressions?

Thanks and regards!

-
I don't understand "For a regular expression, it can also be described by a regular expression." -- could you rephrase that? – joriki Jul 11 '11 at 20:43
@joriki: Thanks for pointing it out. I intended to mean "For a regular <del> expression </del> language, it can also be described by a regular expression." – Tim Jul 11 '11 at 21:13
I'm not sure I follow your definitions. The set of palindromes on a 2-symbol alphabet - is that a formal language? It can't be recognized by a finite state automaton, nor described by a regular expression, if I remember right. – Gerry Myerson Jul 12 '11 at 6:04
@Gerry: My questions are two: (1) Is regular expression some kind of formal grammar? Or at least very close related in the sense that one can be derived trivially from the other? (2) For other non-regular languages which can have formal grammars, is it possible that they can be described by some generalized versions of regular expression? Note that I know they cannot be described by regular expression, or else they would have been regular languages. – Tim Jul 12 '11 at 13:26
Thanks, Tim. I'm out of my depth here, as I don't know what "formal grammar" means. – Gerry Myerson Jul 13 '11 at 1:52

1. 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^*)$$