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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
167 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 ...
TomKern's user avatar
  • 429
7 votes
1 answer
253 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 $...
Bartosz Bednarczyk's user avatar
10 votes
1 answer
332 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}...
Bartosz Bednarczyk's user avatar
0 votes
0 answers
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 ...
J.Doe's user avatar
  • 1
0 votes
0 answers
67 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 ...
Vetrivel's user avatar
2 votes
0 answers
73 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 ...
Bjørn Kjos-Hanssen's user avatar
9 votes
2 answers
280 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 ...
a3nm's user avatar
  • 9,269
4 votes
0 answers
57 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 ...
Denis's user avatar
  • 8,843
8 votes
1 answer
185 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 ...
Denis's user avatar
  • 8,843
0 votes
0 answers
47 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 ...
eatnumber1's user avatar
6 votes
1 answer
211 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}= \...
thibo's user avatar
  • 193
5 votes
1 answer
186 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, ...
ricardorr's user avatar
  • 541
10 votes
1 answer
252 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 ...
Denis's user avatar
  • 8,843
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 ...
Denis's user avatar
  • 8,843
10 votes
1 answer
859 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 ...
Yossi Gil's user avatar
  • 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 ...
honestSalami's user avatar
2 votes
1 answer
175 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 ...
wanderingmathematician's user avatar
3 votes
2 answers
265 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 ...
Mohemnist's user avatar
  • 230
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^* ...
Denis Kyashif's user avatar
3 votes
1 answer
145 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 ...
Armin's user avatar
  • 223
7 votes
1 answer
383 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 ...
Faustus's user avatar
  • 193
7 votes
1 answer
636 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 ...
wlad's user avatar
  • 303
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 ...
ken6208's user avatar
  • 11
9 votes
0 answers
290 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 ...
ghosts_in_the_code's user avatar
6 votes
1 answer
264 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 ...
Armin's user avatar
  • 223
9 votes
0 answers
223 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 ...
Alberto M.'s user avatar
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 ...
Christopher King's user avatar
13 votes
1 answer
767 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 ...
Florent Foucaud's user avatar
2 votes
0 answers
74 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 $...
user1172468's user avatar
5 votes
0 answers
163 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 (...
StefanH's user avatar
  • 2,077
1 vote
0 answers
201 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 ...
Hans-Peter Stricker's user avatar
15 votes
4 answers
722 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 ...
raja.damanik's user avatar
23 votes
1 answer
574 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 $...
mikero's user avatar
  • 2,799
-2 votes
1 answer
253 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 $(...
rega's user avatar
  • 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 ...
Geoffrey Irving's user avatar
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 ...
lukas.coenig's user avatar
2 votes
0 answers
223 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 ...
Andreas T's user avatar
  • 151
2 votes
0 answers
335 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. ...
Wickoo's user avatar
  • 386
4 votes
0 answers
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 ...
damned's user avatar
  • 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, \...
Martin Kristiansen's user avatar
0 votes
0 answers
126 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 ? ...
adi's user avatar
  • 101
-2 votes
1 answer
392 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 ...
manasij7479's user avatar
7 votes
3 answers
856 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 ...
pg1989's user avatar
  • 173
6 votes
3 answers
481 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 ...
Bruno Le Floch's user avatar
3 votes
1 answer
443 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). ...
SBF's user avatar
  • 407
16 votes
2 answers
2k views

minimizing size of regular expression for finite sets

It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification. What are the results if the language is finite? One can ...
Chao Xu's user avatar
  • 4,449
12 votes
1 answer
889 views

The Cost of an Equivalence Query for DFA

Inspired by this question, I am curious about the following: What is the worst-case complexity of checking whether a given DFA accepts the same language as a given regular expression? Is this ...
Lev Reyzin's user avatar
  • 12k
14 votes
1 answer
5k views

What algorithms exist for construction a DFA that recognizes the language described by a given regex?

All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, ...
BlueBomber's user avatar
8 votes
1 answer
352 views

Regular expressions of families of regular expressions

I was reading about the Star Height Problem and noticed that Eggan's family of regular expressions follows a simple pattern which can be described by a regular expression. My question is: are there ...
pseudosudo's user avatar
0 votes
0 answers
131 views

Given a sequence find the shortest reg exp that generates it?

I'm looking for a way to find the smallest possible regular-expression that accepts a sequence. To make it interesting I don't want any stars(Kleene stars) and preferably no wildcards? For instance ...
Martin Kristiansen's user avatar