# Questions tagged [regular-expressions]

Questions about regular expressions, a formalism to describe regular languages.

635 questions
Filter by
Sorted by
Tagged with
174k views

### How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
4k views

### Unusual applications of regular expressions?

I am looking for some interesting applications of regular expressions. Can you name any unusual, or unobvious, cases where regexes find their application?
4k views

### How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively ...
2k views

### Is regex golf NP-Complete?

As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation ...
6k views

### What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages

I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had ...
759 views

346 views

### How hard is finding the shortest path in a graph matching a given regular language?

Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
1k views

### Regular expressions and 'capturing parentheses' with 'backreferences'

We know that regular expressions (RE) are implemented with finite automata (FA). In some language (like JavaScript) in RE there are features like 'capturing parenthesis' with 'backreferences': https:/...
2k views

### Decidability of “Is this regular expression prefix-free?”

Say that string $x$ is a prefix of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it ...
18k views

### Regular Expression to Context-Free Grammar

Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
11k views

### Equivalence of regular expressions [duplicate]

Is it possible, in general, to determine whether two regular expressions admit the same set of strings? Also, in particular, is it possible to determine whether a given regular expression admits the ...
27k views

### Convert DFA to Regular Expression

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first. The provided solution to eliminate $q_2$ is: If we first ...
18k views

### Converting an NFA to regex using GNFA algorithm?

So I've been trying to crack this for a long time and almost feel like I am going in loops about this question. Given the following NFA: Using the GNFA algorithm get the regular expression. I ...
1k views

### How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
2k views

### How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression ...
1k views

### Is it possible to build any regular expression in a computer language with just 3 basic operators?

Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
245 views

### regular expression given the language

The language is: $$L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \}$$ My attempt at an answer: $$(a \cup b)^{3k}$$ This will work if the a OR b can change for each instance in the string that is (...
125 views

### For regular languages A and B, determine whether B might match early in (A B)

I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
110 views

### Relative succinctness of NFAs and regular expressions

What is known about the succintness of NFAs, relative to regular expressions? In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the ...
539 views

### Why are regular expression quantifiers greedy by default?

I can't count the number of times I've seen questions on StackOverflow related to regular expressions where the problem was due to the programmer not understanding the impact of greedy quantifiers. ...
22k views

### Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
497 views

### Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
648 views

### Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
94 views

### Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
1k views

### Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$? A straightforward example: Let's ...
### String of minimum length in $\{a, b\}^*$ not in a regular expression
I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression. a. $b^*(ab)^*a^*$ My answer: \$...