4

I am curious if there is such a regular expression which defines all possible regular expressions. Since there are escape characters that might appear in an RE, it would be tricky to denote such characters in another, say validator, RE since RE's are primarily to describe sequences of alphanumerical characters.

My question can be analogously interpreted as if there is a finite automata which is able to decide a finite-autmata candidate is an FA or not. This is because we know that FA's can be designed in such a way that it rules out a given input string matches the pattern which by the FA is defined or not. So, If we somehow can define everything(FA candidates) as strings, we would be able to define an FA which validates that input is an FA or not. However, I don't know how can I prove this claim, I would be happy if you helped me how I can prove it.

Thanks in advance

bfaskiplar
  • 865
  • 1
  • 7
  • 23
  • so you want a `regex` that can identify if a given text is regex..right? – Anirudha Feb 06 '13 at 18:50
  • if you have control over the input i.e at `User Interface level`..you can distinguish between regex and plain text by providing a textbox or similar thing for the regex **separately**.. – Anirudha Feb 06 '13 at 18:53
  • no, my question is rather theoretical. I question if such a regex could be defined and corresponding finite-automata could be built. – bfaskiplar Feb 06 '13 at 18:55
  • 1
    Regular expressions themselves cannot be described by a regular language (arbitrary nesting of parentheses is one example), so "real" regular expressions are not up for the task. Extended regular expressions (with recursion, backreferences etc.) may be able to do this. – Tim Pietzcker Feb 06 '13 at 19:01
  • Another example is [Regular expression which matches regular expressions](http://stackoverflow.com/questions/2067744/regular-expression-which-matches-regular-expressions?rq=1). – stema Feb 06 '13 at 20:02
  • @Tim Extended REs can't do full nested bracket matching unless they have recursion or something that will work like a counter. – Donal Fellows Feb 06 '13 at 21:02
  • @DonalFellows: I know, I don't mean POSIX EREs, I meant extensions like .NET, Perl, PHP and others have brought to regexes (and these include recursion). – Tim Pietzcker Feb 06 '13 at 21:09

1 Answers1

4

To be able to decide if a RE is "legit", you would need to be able to "count parentheses" to check they are balanced, which you can NOT do with a RE (or FA).

Rodrigo_at_Ximera
  • 548
  • 1
  • 7
  • 9