Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

6
votes
1answer
104 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 ...
1
vote
0answers
37 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 ...
9
votes
0answers
103 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 ...
4
votes
1answer
147 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 ...
9
votes
0answers
176 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 ...
0
votes
0answers
25 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 ...
11
votes
1answer
251 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 ...
0
votes
0answers
37 views

How much of the feature set of regex can be encoded as set operations?

Theoretically, a regex can be viewed as a descriptor on a set of strings that defines membership as "all things that match this regex" vs "all things that don't". For fixed length regexes like '/d[oui]...
2
votes
0answers
72 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 $...
6
votes
0answers
84 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
0answers
157 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
4answers
455 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 ...
21
votes
1answer
333 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 ...
-2
votes
1answer
207 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 $(...
8
votes
1answer
486 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
votes
1answer
1k 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 ...
2
votes
0answers
298 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. ...
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 ...
0
votes
1answer
59 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
0answers
117 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 ? ...
-4
votes
1answer
306 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 ...
7
votes
3answers
570 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 ...
6
votes
3answers
388 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 ...
3
votes
1answer
282 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). ...
14
votes
2answers
847 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 ...
12
votes
1answer
685 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 ...
11
votes
1answer
4k 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, ...
8
votes
1answer
216 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 ...
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 ...
26
votes
3answers
3k views

Known algorithms to go from a DFA to a regular expression

I was wondering whether there is a ``better'' (I will explain in what sense) algorithm to start from a DFA $\mathcal{A}$ and construct a regular expression $r$ such that $L(\mathcal{A})=L(r)$, than ...
27
votes
1answer
1k views

Why are regular languages called “regular”?

Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages. I suppose that, in the beginning, ...
4
votes
2answers
367 views

Matching regular expressions using regular expressions

Is it possible to create a regular expression that matches regular expressions in any given notation? Or, in other words, does there exist a unambiguous and full notation for regular expressions that ...
6
votes
1answer
235 views

Regular expressions without union but with backreferences

As a follow-up to my question Regular expressions without alternation, I was wondering what was known about the power of regular expressions in which union is not allowed but backreferences are. I'm ...
9
votes
1answer
405 views

Regular expressions without alternation

I was wondering about what sets of languages are generated by restrictions of regular expressions. Supposing that all the restrictions have a constant symbol for each element of $\Sigma$ and ...
8
votes
1answer
392 views

Can regexes containing nongreedy (reluctant) quantifiers be rewritten not to use them?

Consider a regex language with the greedy quantifier $*$, the nongreedy quantifier ${*}?$, ordered alternation, and character classes. (This is essentially a sublanguage of PCRE without backreferences,...
6
votes
7answers
1k views

What are regular expressions good for?

If you ask a question about parsing HTML with regex, you will certainly be referenced to this famous rant. Though there is not a canonical rant for it, I've also been told that regex aren't powerful ...
5
votes
5answers
694 views

Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing?

It's well known that a regular expression can be converted to a non-deterministic finite state automaton, which can in turn be converted in to a deterministic finite state automaton. These DFAs can ...
13
votes
2answers
600 views

Progress on generalized star-height problem?

The (generalized) star height of a language is the minimum nesting of Kleene stars required to represent the language by an extended regular expression. Recall that an extended regular expression over ...
4
votes
1answer
2k views

Regular expressions: Finding “negation” of regular expression?

Given regular expressions containing only (,),|,* and characters of an Alphabet A, how can I find the "negation" of a regular expression i.e.: ...
22
votes
2answers
1k views

Protocol partition number and deterministic communication complexity

Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between ...
15
votes
2answers
5k views

Is JSON a Regular Language?

I was wondering if the JSON spec defined a regular language. It seems simple enough, but I'm not sure how to prove it myself. The reason I ask, is because I was wondering if one could use regular ...
10
votes
2answers
494 views

Taxonomy of notable regular expression automata

I'm trying to draw up a taxonomy of algorithms for transforming regular expressions into automata so as to perform some empirical tests of their complexity properties in specific domains. I'm aware ...
2
votes
1answer
445 views

upper bound on the size of a DFA for A|B given the DFAs for A and B?

Given RegEx A and B where the size of the compiled DFAs are m and ...
41
votes
4answers
8k views

Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
30
votes
4answers
1k views

Are there “small” machines which can efficiently match regular expressions?

It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially ...
19
votes
4answers
2k views

Where do most REGEX implementations fall on the complexity scale?

Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do ...
35
votes
6answers
5k views

Regular expressions aren't

Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton. For ...
16
votes
3answers
2k views

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ...