43 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)...
melfnt's user avatar
  • 613
40 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 ...
David Richerby's user avatar
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$ ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Ran G.'s user avatar
  • 20.7k
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 ...
DylanSp's user avatar
  • 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, ...
Gilles 'SO- stop being evil''s user avatar
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) ...
David Richerby's user avatar
18 votes

Unusual applications of regular expressions?

From this page, here's a regex for validating an RFC822-compliant email address ...
BlueRaja - Danny Pflughoeft's user avatar
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 ...
Paŭlo Ebermann's user avatar
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 ...
StefanH's user avatar
  • 1,439
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 = ...
Yuval Filmus's user avatar
16 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 ...
C8H10N4O2's user avatar
  • 746
15 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, ...
Yuval Filmus's user avatar
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 ...
Hendrik Jan's user avatar
  • 30.6k
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.
Pseudonym's user avatar
  • 22.1k
13 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. ...
benrg's user avatar
  • 2,112
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^{*}$.
kaya3's user avatar
  • 520
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 ...
Joey Eremondi's user avatar
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 ...
Steven's user avatar
  • 29.5k
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 ...
Yuval Filmus's user avatar
11 votes

Why are regular expressions defined with union, concatenation and star operations?

The technical report that introduced regular languages, regular expressions, and finite automata asks your question on page 70: The question may occur to the reader, why did we select the ...
reinierpost's user avatar
  • 5,529
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$ ...
Yuval Filmus's user avatar
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 ...
Olivier Dulac's user avatar
10 votes

Why isn't it simple to count the number of words in a regular language?

Complementing jmite's answer, it is not too difficult to compute the number of words in a regular language, using the "transfer matrix" method. This is the same as jmite's dynamic programming, but the ...
Yuval Filmus's user avatar
10 votes

Unusual applications of regular expressions?

One of the best ones I've seen using regex is to 'shift a number right by half a bit', i.e. to divide a number by $\sqrt 2$ and return the closest integer! Take a look at @Deadcode's Code Golf answer ...
Nihar Karve's user avatar
9 votes

Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

If you only wanted to parse regular expressions then you wouldn't have such problems (unless you were a really incompetent programmer, I guess). Caveats include the time needed to build an automaton; ...
Raphael's user avatar
  • 72.4k
9 votes
Accepted

Does a regular expression model the empty language if it contains symbols not in the alphabet?

Regular expressions only use characters from the alphabet so, if you've fixed your alphabet to be $\{a,b\}$, then $(a^∗b+dc)^∗(b^∗d+ad)^∗$ isn't a regular expression. It doesn't describe any language, ...
David Richerby's user avatar
9 votes

Regular expressions and 'capturing parentheses' with 'backreferences'

These extended notions of regular expressions capture more than just the regular languages. For example, ([ab]*)\1 matches the language $\{ww\mid w\in\{a,b\}^*\}$, ...
David Richerby's user avatar
9 votes

Why isn't it simple to count the number of words in a regular language?

Actually, you can still derive counting formulas for unambiguous regular expressions with Kleene stars within. Given the inductive definition of a regular expression as: $$ \begin{equation*} e \in \...
Lee's user avatar
  • 1,097

Only top scored, non community-wiki answers of a minimum length are eligible