40
I don't know if this question belongs here (the answer could be subjective and depend on your definition of "unusual") but here is my favorite unusual application of regex:
converting T9 input (2-9) to English text.
For example if the user wants to write hello they presses 42556. Convert the input to [ghi][def][jkl][jkl][mno] and test this regex against ...
38
The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's ...
25
Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe non-regular languages. For example, (.*)\1 describes the language $\{ ww : w \in \Sigma^* \}$, which is not even context-free.
24
Whoever told you that regular expressions are used to parse code was spreading disinformation. Classically (I don't know to what extent this is true in modern compilers), the parsing of code – conversion of code from text to a syntax tree – is composed of two stages:
Lexical analysis: Processes the raw text into chunks such as keywords, numerical constants, ...
23
Regular expressions, regular grammars and finite automata are simply three different formalisms for the same thing. There are algorithms to convert from any of them to any other.
The basic reason that we have all three is that they were created independently, with the first set of equivalences (there are several other formalisms as well) proven by Kleene (...
23
If regular expressions were allowed to be infinite, then any language would have been regular.
Given the language $L=\{w_1, w_2, \ldots\}$, we can always define the regular expression $R = w_1 + w_2 + \cdots$, which exactly defines $L$.
(Example: the regular expression $R_1 = \epsilon+0+1+00+01+10+11+\cdots$ defines $L_1=\{0,1\}^*$.)
We know that some ...
19
Since you want "to convert regex to DFA in less than 30 minutes", I suppose you are working by hand on relatively small examples.
In this case you can use Brzozowski's algorithm $[1]$, which computes directly the Nerode automaton of a language (which is known to be equal to its minimal deterministic automaton). It is based on a direct computation of the ...
19
With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \{ab\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$. With only ...
18
You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) might have defined them as any of
languages described by regular expressions;
languages accepted by deterministic finite automata (DFAs);
languages accepted ...
17
Indeed the POSIX BRE language cannot express all regular expressions because it lacks alternation. It can't even recognize all finite languages, let alone all regular languages.
For example, $\{ab, ba\}$ is not recognizable as a BRE. To prove this, consider what the toplevel syntactic form could be:
It can't be one of the single-character forms since the ...
answered Aug 27 '16 at 19:46
Gilles 'SO- stop being evil'
39.2k7 gold badges103 silver badges167 bronze badges
17
From this page, here's a regex for validating an RFC822-compliant email address
(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:
\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(
?:\r\n)?[ \t])+|\Z|(?=[\[...
16
A set is closed under some operator if the result of applying the operator to things in the set is always in the set. For example, the natural numbers are closed under addition because, whenever $n$ and $m$ are natural numbers, $n+m$ is a natural number. On the other hand, the naturals are not closed under subtraction since, for example, $3-5$ is not a ...
16
1) If we also allow intersection and complement, then the resulting expressions are sometimes called extended regular expressions; as the regular languages are closed under boolean operations nothing is gained by them. It is just syntactic sugar. A similar conclusion holds for the reverse operation. Part of the reason why on first instance all the other ...
16
The pumping lemma states a proprety of regular languages:
If $L$ is a regular language then there exists an integer $p$ such that if $w \in L$ has length at least $p$ then it can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.
Unfortunately, this property doesn't characterize regular languages. That ...
16
So my question is:
(Why) Is my proof wrong?
If it is right: Why is there no easy way to express permutations?
Your "proof" only looked at permutations of single words, which are finite languages.
Every finite language is regular (e.g. just by listing all of the members with a | inbetween), but there are infinite regular languages (and those ...
15
Assuming the TCS-variant of regex, the problem is indeed NP-complete.
We assume that our regexes contain
letters from $\Sigma$, matching themselves,
$+$, denoting union,
$\cdot$, denoting concatenation,
$*$, denoting Kleene-Star,
$\lambda$, matching the empty string
and nothing else. Length of a regex is defined as the number of characters from $\Sigma$. ...
14
tl;dr backrefs.
As soon as there is a \1 (or any number that isn't used to escape unicode) in the regexp it is not a regular expression.
Backrefs allows you to match (a+)b\1 which matches n times a followed by b followed by n times a for any n>1. This is not a regular language (it's the poster child of a non regular language).
It is necessary and nearly ...
14
It depends upon whether you've got a regular expression or a regexp: regexps are evil, but regular expressions are a thing of beauty and will never turn evil on you.
By regexp, I mean a modern regular expression: i.e., a regular expression with additional modern features such as backreferences -- e.g., a Perl-compatible regular expression. This is more ...
14
First, notice that you can easily eliminate $\emptyset$ for all regular expressions other than a regular expression describing the empty language. To do this, you use the following rewriting rules, which define an operator $E$ on regular expressions:
$E[\sigma] = \sigma$, $E[\epsilon] = \epsilon$, $E[\emptyset] = \emptyset$.
$E[r_1 r_2]$ is $\emptyset$ if ...
13
Again, I don't know how unusual it is, but Paul Heckbert introduced regular expressions in path tracing to distinguish the light transport paths that various algorithms can correctly solve.
12
The authoritative reference on the pragmatic issues behind implementing regex engines is a series of three blog posts by Russ Cox. As described there, since backreferences make your language non-regular, they are implemented using backtracking.
Lookaheads and lookbehinds, like many features of of regex pattern matching engines, don't quite fit into the ...
12
Hendrik Jan gives a good answer for complexity class, but not an algorithm itself.
The simplest algorithm to do this that I know of is to convert the regular expression to a DFA. There are known techniques for converting a regular expression to an NFA, and an NFA to a DFA.
Once you have two DFAs, testing for equivalence is efficient and decidable, since ...
12
This is some heavy stuff for a high school assignment.
Yuval Filmus's answer is really good, so this is more of a supplementary answer to clarify some of the points he made.
A formal language is a mathematical construction. Their use for programming languages is just one of many possible uses; in fact, linguist Noam Chomsky made significant contributions ...
12
Yep, this is wrong, because of ambiguity.
Consider the following language:
$(a + aa) + a(a + \epsilon)$.
With your method, we see 4 words, $a, aa, aa, a$. But we have duplicates! There are multiple ways to make the same word within the given regular expression.
A better method is to use dynamic programming on an minimal DFA for your language, with no "...
12
How about fighting cancer with the power of regex?
https://www.sciencedirect.com/science/article/pii/S2352914819303120
Title: Regular expression based pattern extraction from a cell - Specific gene expression data
Abstract: Cancer cells are formed when active genes stop functioning properly. Timely activation of a gene is governed through the ...
11
First, the string of minimum length might not be defined properly since it might not be unique.
Here is a way to find a string of minimum length:
Convert the regular expression to a nondeterministic finite automaton.
Convert the nondeterministic automaton into a deterministic one.
Use a breadth first search until you encounter the first nonfinal state (if ...
11
Equivalence of regular expressions is known to be PSPACE-complete, which is rather bad. The paper "Complexity of Decision Problems for Simple Regular Expressions" lists several subclasses of regular expressions with their respective complexities. (link)
11
The set $1^*+0^*$ is composed of two parts: $1^*$ and $0^*$. The first part, $1^*$, is all strings composed entirely of $1$s. The second part, $0^*$, is all strings composed entirely of $0$s. In contrast, $(1+0)^*$ is all strings composed of $0$s and $1$s. Can you now think of a string in $(1+0)^*$ but not in $1^*+0^*$?
11
The problem is NP-hard.
We show this by reducing vertex cover:
Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V'$?
We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows:
All columns, except for the ...
11
Minimizing NFAs is known to be PSPACE-hard: Meyer and Stockmeyer showed that given an NFA, it is PSPACE-hard to find the size of the minimal equivalent NFA, and Jiang and Ravikumar showed that given a DFA, finding the size of the minimal equivalent NFA is PSPACE-hard. Later some hardness of approximation results were proved, showing that it is even hard to ...
Only top voted, non community-wiki answers of a minimum length are eligible
