2
$\begingroup$

Are the ones in modern programming languages equivalent to, say, Context-Free Grammars or is there an intermediate (between finite automata and CFGs) set of languages that it covers?

$\endgroup$
  • 2
    $\begingroup$ (Coming to mind are contexts / lookahead (a(?=b)) and (backward) references ((a+)b\1b\1 - there is a reason this is not mentioned 1st).) $\endgroup$ – greybeard Feb 9 at 9:01
2
$\begingroup$

A famous example: a PCRE that finds primes. I couldn’t find Abigail’s original, but there have been many iterations on this.

In JavaScript, for example, you can pass a function to the matcher to do arbitrary computation with the results.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Here is a specific example, POSIX EREs (Extended Regular Expressions).

POSIX EREs have, on top of the computer science definition, back-references for the first 9 capturing groups. This gives some extended properties, like being able to match the $a^nba^nba^n$ via the regex \(a*\)b\1b\1, which cannot be matched by any context-free grammars.

However, POSIX EREs cannot match $a^nb^n$ despite this language being context-free.

Thus to answer your question, "or is there an intermediate (between finite automata and CFGs) set of languages that it covers?", POSIX EREs do match an intermediate, but it is not strictly between finite automata and CFGs, as mentioned with the example languages given above. In fact, you can have an infinite hierarchy of such regular expressions based on POSIX EREs, each having increased maximum number of capturing groups that can be back-referenced.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

In programing languages, or their libraries, functions for handling regular expressions are not interested in languages, they are interested in detecting things. For example, take the text of an e-mail and detect a phone number inside it.

There is no reason to restrict regular expressions to those in computer science. For example, $a^n b^n$ is not a regular language, but quite easy to detect. (Yes, there's an infinite number of states. A 64 bit counter can practically represent an infinite number of states - enough to recognise any string that fits on one million large hard drives). Or take the situation where you want two substrings to be the same. Not regular, but easy enough to program.

So "regexes" in programming languages will recognise strings where the rules can be described easily, and that can be recognised with reasonable programming effort, without any regard for computer science.

(As an example, a recent question asked: Given a regular language L, is the language { w: ww element of L } a regular language? Turns out, no. But it is easily recognised. Give me a string w, I write down ww and check if it is in L. )

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

In POSIX ERE (extended regular expressions) you can write ^([a-z]*)\1$ (here (...) captures a match, which is repeated by \1 later, ^ matches the beginning of a line, $ it's end), which represents the language $\{\omega \omega \colon \omega \in \Sigma^*\}$ (the alphabet being lowercase letters), which isn't even context free.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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