Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted
  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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.