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

66 questions
Filter by
Sorted by
Tagged with
46 views

### Proving the Equivalence of REGEX r^n and r^{..n} when r Is Nullable

Im seeking clarification and a rigorous proof regarding the equivalence of r^n and r^{..n} in the context of formal languages, particularly when r is nullable. To clarify the terminology: r denotes ...
62 views

### How to reduce a code down to its configuration

I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ...
72 views

### Languages free of concatenations of stars

Union-free regular languages, defined by regular expressions (using $*$, literals (alphabet symbols), and concatenation) excluding union (written $+$ or $\cup$) have been studied. Note that unions ...
266 views

### Defining regular language classes with disjoint union

Regular languages are typically defined using the operations of union, concatenation, and Kleene star. Likewise, there are restricted classes of regular languages defined via similar operations, for ...
55 views

### Reference for cost of translating between regular language formalisms

It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO). The cost (say in size ...
177 views

### Word equations with integer parameters

This is mainly a reference request. Let us define a parameterized expression on a finite alphabet $\Sigma$ as follows: $$e,e':= w\mid w^i \mid e\cdot e'$$ Where $w\in\Sigma^+$ is a word, and $i$ is an ...
43 views

### Regex: Pre-determining the position of matching characters

For all regular expressions, is it possible to pre-determine the set of possible positions in which any given sub-expression may be found? If so, is there any existing research on this subject? Here's ...
203 views

158 views

### Salomaa's axiomatisation of regular languages and the use of regular expression in it

I am reading the classical article of A. Salomaa where he gives two axiom systems for regular sets and proofs consistency and completeness. As I have understood it, an axiomatic system in some logic (...
1 vote
199 views

### Hysteresis in finite automata

The concept of hysteresis seems well suited to describe and distinguish finite automata: "Hysteresis is the dependence of the state of a system on its history." (Wikipedia, Hysteresis) "[The ...
713 views

### Hierarchies in regular languages

Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture ...
562 views

1k views

### Fully linear time regular expression matching

Is there an $O(n+m)$ algorithm to check whether a size $n$ regular expression matches a size $m$ string, assuming a fixed size alphabet if that matters? The standard NFA algorithm is $O(nm)$ worst ...
3k views

### How can one ACTUALLY minimize a regular expression? [closed]

Minimizing regular expressions (in terms of number of symbols) is PSPACE-complete (for example as discussed here: minimizing size of regular expression). But how do you actually do that (i.e., what ...
222 views

### Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
334 views

### Composition of regular expressions with lookahead into DFAs

Let's say we have a regular expression ("a" | "b"(~!"b"))*, written in Perl or other similar languages that support lookahead, which should match a list of a and b's where b's are not followed by b's. ...
92 views

### Sub optimal regex equivalence

Regex Equivalence is a hard problem which in general takes exponential space and exponential time. Are there any approximation/sub-optimal algorithms with some theoretical guarantees over equivalence ...
60 views