# Questions tagged [regular-expressions]

Questions about the theory of regular expressions, both in the sense of Kleene's original definition and of POSIX regular expressions.

74 questions
Filter by
Sorted by
Tagged with
144 views

### Minimum Regular Expression for Strings not Containing Substring?

Given an alphabet $\Sigma$ and a fixed nonempty string $w$, consider the problem of finding a minimum regular expression $R(\Sigma, w)$ for all strings in $\Sigma^\star$ that do not contain $w$ as a ...
97 views

### How to find regular expression using ardent's rule for recursive expressions? [closed]

I have the following automata: States = {A,B} Transitions = { (A,0,A), (B,0,B), (A,1,B), (B,1,A) } Initial state = A Final state = B Inputs = {0,1} Here if I try ...
• 5
105 views

### How large are the Brzozowski Derivatives?

In Brzozowski's original paper [1], he considers two expressions ACI-equivalent, if they can be simplified into one another using the following axioms: Associativity: $r + (s + t) \equiv (r + s) + t$ ...
66 views

146 views

### Are all RegExp solvable in O(n)?

I'm wondering if all features, that are often part of modern RegEx engines, are solvable in O(n). I'm talking about features like repeating patterns ([abc]+);\1 ...
• 223
399 views

### Kleene Algebra for star-free regular expressions

TLDR: Is there a notion of Kleene Algebra for star-free regular expressions? Kleene Algebras are algebraic structures that are equivalent to regular expressions. A Kleene Algebra is an idempotent ...
• 193
691 views

### Time complexity of derivative-based regex matchers

Regex matching using the Brzozowski derivative without any caching or expression-simplifying takes exponential time and space because of the product rule. In Brzozowski's original paper, Brzozowski ...
• 323
1 vote
48 views

### Question About Turing Machine Computability [closed]

If p is a Turing machine then L(p) = {x | p(x) = yes}. Let A = {p | p is a Turing machine and L(p) is a finite set}. Is A computable? Justify your answer. So I'm trying to figure out how to solve ...
• 11
299 views

### Shortest string in the intersection of regular languages

Inspired by https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string Each of the 138,172 valid mazes can be represented as a DFA with 9 states (including starting and ...
270 views

### How powerful is POSIX regex

The set of languages recognized by POSIX regex is a true superset of type 3 languages. But how powerful is POSIX regex really? Is it in an already known class? Is it its own class? If so, what is the ...
• 223
225 views

### Regular expressions of prefixes/suffixes

It is well-known that star-free regular expressions, which are defined by the grammar $r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$ where $a$ belongs to a finite ...
• 151
35 views

### Searchable finite field

Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$). We say that $F$ is searchable if ...
858 views

### Parameterized complexity of inclusion of regular languages

I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed ...
• 2,153
75 views

• 2,809
255 views

127 views

### Is it possible to simulate a regular expression using a single stack?

I understand that a regular expression can be converted to an equivalent DFA which can then be simulated. However, is it possible to simulate the regular expression directly with the aid of a stack ? ...
• 101
398 views

### Can I show algebraically that this regular expression accepts all binary strings?

The task is to prove that (0+1)* and 0*(1.0*)* are equivalent. 1. http://rubular.com/r/K9Hp9tU6px 2. http://rubular.com/r/N8VpoEcch4 EDIT: Forgot that + was ambiguous here! I want to prove that the ...
• 131
860 views

### Algorithm for ranking members of a regular language?

A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines ...
• 173
I know of the Chomsky hierarchy, which concerns the expressive power of grammars to recognize languages $L \subseteq \Sigma^*$ made of words on an alphabet $\Sigma$. Is there a similar hierarchy for ...