41
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)...
- 593
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.2k
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$ ...
- 270k
25
votes
Accepted
What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages
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 – ...
- 270k
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.7k
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 ...
- 270k
23
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.4k
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.4k
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,924
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 ...
- 875
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.2k
18
votes
Unusual applications of regular expressions?
From this page, here's a regex for validating an RFC822-compliant email address
...
17
votes
Accepted
Why is the Kleene star operator also called the Kleene 'closure' operator?
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$ ...
- 80.2k
17
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, ...
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
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,379
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 = ...
- 270k
15
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,108
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.♦
- 141k
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, ...
- 270k
14
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 ...
- 726
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.
- 18.9k
12
votes
What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages
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 ...
- 3,068
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.1k
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,399
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 ...
- 23.4k
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.3k
11
votes
Accepted
Are regex crosswords NP-hard?
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$ ...
- 6,519
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 ...
- 270k
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 ...
- 270k
Only top scored, non community-wiki answers of a minimum length are eligible