0
$\begingroup$

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!

  • 0
    Thanks, Tim. I'm out of my depth here, as I don't know what "formal grammar" means.2011-07-13

1 Answers 1

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

  2. 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.