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 ...
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$ ...
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 ...
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 ...
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) ...
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 ...
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 ...
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 = ...
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 ...
  • 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, ...
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 ...
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-...
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 ...
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 ...
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$ ...
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 ...

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