Questions about the theory of regular expressions, both in the sense of Kleene's original definition and of POSIX regular expressions.

learn more… | top users | synonyms

2
votes
0answers
56 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. ...
3
votes
0answers
67 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
57 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
86 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 ? ...
-5
votes
1answer
218 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
270 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
271 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
186 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
567 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
382 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 ...
7
votes
1answer
1k 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, ...
7
votes
1answer
190 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
118 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 ...
21
votes
3answers
2k 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 ...
19
votes
1answer
696 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
325 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
179 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
330 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
373 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 ...
4
votes
6answers
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
341 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 ...
10
votes
1answer
368 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 ...
2
votes
1answer
1k 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
939 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 ...
8
votes
2answers
2k 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
410 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
311 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 ...
29
votes
4answers
5k 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). ...
27
votes
4answers
981 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 ...
14
votes
4answers
1k 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 ...
27
votes
6answers
4k 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 ...
14
votes
3answers
1k 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 ...