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.

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
143 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 ...
9
votes
0answers
180 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 ...
5
votes
0answers
88 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 (...
4
votes
0answers
82 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 ...
2
votes
0answers
310 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. ...
1
vote
0answers
167 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 ...
0
votes
0answers
26 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 ...
0
votes
0answers
119 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 ? ...
0
votes
0answers
124 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 ...