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)...
user avatar
  • 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 ...
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$ ...
user avatar
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 – ...
user avatar
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 ...
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 ...
user avatar
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 +...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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) ...
user avatar
18 votes

Unusual applications of regular expressions?

From this page, here's a regex for validating an RFC822-compliant email address ...
user avatar
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$ ...
user avatar
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, ...
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 ...
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 ...
user avatar
  • 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 = ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

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