42
votes
Unusual applications of regular expressions?
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)...
- 603
39
votes
Accepted
Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)
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 ...
- 80.9k
31
votes
Accepted
Proving Equivalence of Two Regular Expressions
One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions:
Show that if $w$ is generated by $r_1$ then it is generated by $r_2$.
Show that if $w$ ...
- 273k
25
votes
Accepted
Difference between regular expression and grammar in automata
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 ...
- 17.9k
25
votes
Accepted
Is it possible to build any regular expression in a computer language with just 3 basic operators?
Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe ...
- 273k
24
votes
Accepted
Can a regular expression be infinite?
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 +...
- 20.5k
22
votes
Accepted
What is the correct way to draw NFA of RE (a|b|c)?
There is no unique way of converting a regex into NFA. That is, for any regular language $L$ there exist multiple (even, infinite) number of NFAs that accept the language $L$.
The solution of your ...
- 20.5k
21
votes
How to create DFA from regular expression without using NFA?
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 ...
- 5,934
19
votes
Accepted
Regular languages that can't be expressed with only 2 regex operations
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 ...
- 865
18
votes
Accepted
Can POSIX BRE express all regular languages?
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, ...
18
votes
How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
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) ...
- 80.9k
18
votes
Unusual applications of regular expressions?
From this page, here's a regex for validating an RFC822-compliant email address
...
17
votes
Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)
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 ...
- 523
16
votes
Accepted
When is a regexp not a Regular Expression?
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 ...
- 4,224
16
votes
Accepted
Why are regular expressions defined with union, concatenation and star operations?
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 ...
- 1,429
16
votes
Accepted
How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?
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 = ...
- 273k
15
votes
Unusual applications of regular expressions?
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 ...
- 736
14
votes
For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?
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 ...
D.W.♦
- 150k
14
votes
Accepted
How to determine minimum word length of regular language
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, ...
- 273k
14
votes
Accepted
Non-regular language whose prefix language is regular but not the whole set of words
If there are no further rules, then there is a simple solution. In any existing example double all symbols in each string. That is, change the symbols $0$ and $1$ by the pairs $00$ and $11$. Formally ...
- 29k
13
votes
Unusual applications of regular expressions?
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.
- 19.8k
13
votes
Non-regular language whose prefix language is regular but not the whole set of words
Here's a quite simple example: the language $\{a^m b^{mn} : m, n \in \mathbb{N}\}$ is not regular, but its prefix language is recognised by the regular expression $\epsilon \mathop{|} a a^{*} b^{*}$.
- 393
12
votes
Why isn't it simple to count the number of words in a regular language?
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 ...
- 29.4k
12
votes
Theory behind regex implementations
It isn't a matter of implementation. It's a matter of different approaches to parsing that unfortunately have similar names.
NFAs and DFAs (finite-state machines) can only recognize regular languages. ...
- 1,768
12
votes
Accepted
I have found an example where regular expression is not closed under concatenation. Where am I wrong?
If $n$ is fixed then $a^n$ is just a single word and so is $a^nb^n$.
If by $a^n$ you mean the language $\{a^n \mid n \ge 0\}$ (whose corresponding regular expression is $a^*$) then the problem is that ...
- 26k
11
votes
How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?
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-...
- 17.5k
11
votes
Does Thompson's algorithm produce optimal NFAs?
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 ...
- 273k
11
votes
Regular languages that can't be expressed with only 2 regex operations
A perhaps more interesting question is that of star height. The other answer mentions that if you can't use star, then you can only generate finite languages. What if you are not allowed to nest stars ...
- 273k
11
votes
Accepted
Can we convert an NFA to a regular expression of polynomial length?
Using the concept of star height, Gruber and Holzer showed in Finite Automata, Digraph Connectivity, and Regular Expression Size that there exists a constant $C>1$ and a sequence of languages $L_n$ ...
- 273k
11
votes
Unusual applications of regular expressions?
A simple PCRE expression (not exactly an regular expression, this one includes a +?) can say if an unary number is non-prime (so when it doesn't match, the unary ...
- 219
Only top scored, non community-wiki answers of a minimum length are eligible