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
4
votes
0
answers
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 ...
- 613
-2
votes
1
answer
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
6
votes
0
answers
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$
...
2
votes
0
answers
66
views
Complexity of FirstMatch (Prefix Elimination) Operator for regular expressions
Consider the operator $\texttt{FirstMatch} : 2^{\Sigma^*} \to 2^{\Sigma^*}$ defined as follows:
$$\texttt{FirstMatch}(L) = \left \{ y \mid y \in L, \forall \text{ prefixes } x \text{ of } y, x \not \...
1
vote
1
answer
107
views
Equivalence of regex in Programming language theory
I'm studying about the regular expression, but I'm a little confused about the concept of 'equivalence'. When I want to check "[[r]] ≡ [[ε]]", it's false if r is NULL, true if epsilon, false ...
- 13
3
votes
1
answer
180
views
Is it useful to "untangle" an NFA by converting to a regular expression and back
Consider the following recursive algorithm for converting a regular expression into a transition diagram for an NFA with epsilon-edges (freely, optionally traversible edges), one start state and one ...
- 519
7
votes
1
answer
258
views
Are regular expressions polynomially decomposable?
This question is related to my previous question (LINK).
I would like to ask whether regular expressions can be polynomially decomposed in the following sense:
A regular expression $\mathcal{R}$ is $...
- 1,347
11
votes
1
answer
373
views
The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states
Suppose that a regular expression $\mathcal{R}$ over an alphabet $\Sigma$ is given. It is well-known that one can now construct a non-deterministic finite automaton $\mathcal{A}$ such that $\mathcal{R}...
- 1,347
0
votes
0
answers
49
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 ...
- 1
0
votes
0
answers
69
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 ...
- 99
2
votes
0
answers
79
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 ...
- 4,485
9
votes
2
answers
302
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 ...
- 9,697
4
votes
0
answers
58
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 ...
- 8,923
8
votes
1
answer
188
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 ...
- 8,923
0
votes
0
answers
71
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 ...
- 109
6
votes
1
answer
220
views
star height of star-free languages
I'm interested in the (restricted) star-height of star free-languages.
Recalling the definitions:
the star height $h(\mathtt{e})$ of a regular expression $\mathtt{e}$ is
$0$ if $\mathtt{e}= \...
- 193
5
votes
1
answer
195
views
Regular Expressions that converts into unambiguous automata
Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...
- 561
10
votes
1
answer
256
views
Succinctness of regular expressions with empty word
Consider regular expressions on some alphabet $\Sigma$, without the empty word: $$e,f:=a\in\Sigma\mid e\cdot f \mid e+f\mid e^+$$
These $\varepsilon$⁻free expressions can define all regular languages ...
- 8,923
5
votes
0
answers
95
views
Complexity of inclusion of transfinite expressions
Transfinite expressions on an alphabet $\Sigma$ are generated by the grammar :
$$e,f:= a\in\Sigma\mid e\cdot f\mid e+f\mid e^*\mid e^\omega.$$
They describe languages of transfinite words, i.e. words ...
- 8,923
10
votes
1
answer
892
views
Ambiguity of regular expressions
Some regular expressions are ambiguous. Some are not. a*b* is unambiguous for example. Expression a*a* is ambiguous but it can ...
- 531
2
votes
0
answers
78
views
Is there a list of notations developed for regular expressions? [closed]
There is, of course, PCRE.
I know also of Olin Shiver's Structural Regular Expressions, and Rob Pike's Structural Regular Expressions.
I also understand that Raku's regexps are different from perl's ...
- 121
2
votes
1
answer
176
views
What graphs on $\mathbb{N}$ can be encoded as regular languages?
Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers ...
3
votes
2
answers
284
views
Match a string agains a set of regexes
There are several algorithms to match a (simple) string against a regular expression (see here).
But if we have a lot of regexes, can we find one of them that matches the given string faster than ...
- 240
3
votes
1
answer
140
views
Rewrite relations - proof of correctness
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := Id(\Sigma^* ...
3
votes
1
answer
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
7
votes
1
answer
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
9
votes
1
answer
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
0
answers
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
9
votes
0
answers
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 ...
6
votes
1
answer
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
9
votes
0
answers
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
0
votes
0
answers
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 ...
- 481
13
votes
1
answer
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
2
votes
0
answers
75
views
Have people explored the problem of regular expressions being matchable? [closed]
I ran into a problem of determining if two regular expressions would have any possible matches in common. For example:
Fo*bar and Fo+bar
More specifically:
if $...
- 121
5
votes
0
answers
172
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 (...
- 2,057
1
vote
0
answers
202
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 ...
15
votes
4
answers
734
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 ...
- 183
23
votes
1
answer
589
views
For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?
It is well known that the following problem is PSPACE-complete:
Given regular expression $\beta$, does $L(\beta) = \Sigma^*$?
What about determining equivalence to other (fixed) regular expressions $...
- 2,809
-2
votes
1
answer
255
views
Writing a regular expression for character set $\Sigma = \{a,b,(,)\}$ that not have a parenthesis inside a parenthesis [closed]
Let character set $\Sigma=\{a,b,(,)\}$. I want to write a regular expression for the language $L$ that does not have a parenthesis inside a parenthesis.
For example, $(abaab)(bbbaa) \in L$, while $(...
- 1
9
votes
1
answer
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 ...
- 3,263
5
votes
1
answer
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 ...
- 169
2
votes
0
answers
227
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 ...
- 151
2
votes
0
answers
336
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.
...
- 386
4
votes
0
answers
94
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 ...
- 141
0
votes
1
answer
62
views
Finding containing sets, within sets of sets
Let $s = \{\sigma_1, \sigma_2 \ldots \sigma_n\}$, where $\sigma_i \in \Sigma$, denote a set of alphabet characters.
And $s \in S$ where $S$ denotes a set of sets.
Given a new set $s' = \{\sigma'_1, \...
0
votes
0
answers
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
-2
votes
1
answer
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
7
votes
3
answers
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
7
votes
3
answers
488
views
Chomsky hierarchy for tree structures
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 ...
- 293
3
votes
1
answer
447
views
Deterministic Büchi + its complement covers LTL?
It is well known that deterministic Büchi automata (DBA) are less expressive than non-deterministic Büchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). ...
- 407