# Tag Info

### 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)...
• 613
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 ...
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$ ...
• 278k
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 ...
• 278k
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.7k
Accepted

• 278k

### 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 ...
• 746
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, ...
• 278k
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 ...
• 30.7k

### 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.
• 22.5k

### 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. ...
• 2,192

### 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^{*}$.
• 520

### 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.8k
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 ...
• 29.5k

### 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 ...
• 5,746
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$ ...
• 278k

### 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 ...

### 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 ...
• 278k

### 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 ...
• 201

### 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; ...
• 72.6k
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, ...

### 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\}^*\}$, ...

### 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 \...
• 1,097