94
There are several methods to do the conversion from finite automata to regular expressions. Here I will describe the one usually taught in school which is very visual. I believe it is the most used in practice. However, writing the algorithm is not such a good idea.
State removal method
This algorithm is about handling the graph of the automaton and is ...
50
Method
The nicest method I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods.
Let $A= (Q,\Sigma,\delta,q_0,F)$ an NFA without $\varepsilon$-transitions. For every state $q_i$, create the equation
$\qquad \...
34
Your conjecture is disproved by Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang in their paper "Regular Expressions: New Results and Open Problems". While the paper is not available on-line, a talk is.
In the paper, they define the measure $|\mathrm{alph}(R)|$, which is the number of symbols in $R$, not counting $\epsilon$ or $\emptyset$. ...
34
The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's ...
28
Brzozowski algebraic method
This is the same method as the one described in Raphael's answer, but from a point of view of a systematic algorithm, and then, indeed, the algorithm. It turns out to be easy and natural to implement once you know where to begin. Also it may be easier by hand if drawing all the automata is impractical for some reason.
When ...
24
Transitive closure method
This method is easy to write in a form of an algorithm, but generates absurdly large regular expressions and is impractical if you do it by hand, mostly because this is too systematic. It is a good and simple solution for an algorithm though.
The key idea
Let $R^k_{i,j}$ represent the regular expression for the strings going from ...
24
Whoever told you that regular expressions are used to parse code was spreading disinformation. Classically (I don't know to what extent this is true in modern compilers), the parsing of code – conversion of code from text to a syntax tree – is composed of two stages:
Lexical analysis: Processes the raw text into chunks such as keywords, numerical constants, ...
23
If regular expressions were allowed to be infinite, then any language would have been regular.
Given the language $L=\{w_1, w_2, \ldots\}$, we can always define the regular expression $R = w_1 + w_2 + \cdots$, which exactly defines $L$.
(Example: the regular expression $R_1 = \epsilon+0+1+00+01+10+11+\cdots$ defines $L_1=\{0,1\}^*$.)
We know that some ...
22
Regular expressions, regular grammars and finite automata are simply three different formalisms for the same thing. There are algorithms to convert from any of them to any other.
The basic reason that we have all three is that they were created independently, with the first set of equivalences (there are several other formalisms as well) proven by Kleene (...
21
First of all, backreferences can not be simulated by finite automata as they allow you to describe non-regular languages. For example, ([ab]^*)\1 matches $\{ww \mid w \in \{a,b\}^*\}$, which is not even context-free.
Look-ahead and look-behind are nothing special in the world of finite automata as we only match whole inputs here. Therefore, the special ...
19
With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \{ab\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$. With only ...
18
Since you want "to convert regex to DFA in less than 30 minutes", I suppose you are working by hand on relatively small examples.
In this case you can use Brzozowski's algorithm $[1]$, which computes directly the Nerode automaton of a language (which is known to be equal to its minimal deterministic automaton). It is based on a direct computation of the ...
18
You can't. The pumping lemma can only be used to prove that a language is non-regular. How to prove that it is regular depends on how you've defined regular languages. You (or your course or textbook) might have defined them as any of
languages described by regular expressions;
languages accepted by deterministic finite automata (DFAs);
languages accepted ...
17
Indeed the POSIX BRE language cannot express all regular expressions because it lacks alternation. It can't even recognize all finite languages, let alone all regular languages.
For example, $\{ab, ba\}$ is not recognizable as a BRE. To prove this, consider what the toplevel syntactic form could be:
It can't be one of the single-character forms since the ...
16
1) If we also allow intersection and complement, then the resulting expressions are sometimes called extended regular expressions; as the regular languages are closed under boolean operations nothing is gained by them. It is just syntactic sugar. A similar conclusion holds for the reverse operation. Part of the reason why on first instance all the other ...
16
The pumping lemma states a proprety of regular languages:
If $L$ is a regular language then there exists an integer $p$ such that if $w \in L$ has length at least $p$ then it can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.
Unfortunately, this property doesn't characterize regular languages. That ...
15
All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with ...
15
A set is closed under some operator if the result of applying the operator to things in the set is always in the set. For example, the natural numbers are closed under addition because, whenever $n$ and $m$ are natural numbers, $n+m$ is a natural number. On the other hand, the naturals are not closed under subtraction since, for example, $3-5$ is not a ...
14
Assuming the TCS-variant of regex, the problem is indeed NP-complete.
We assume that our regexes contain
letters from $\Sigma$, matching themselves,
$+$, denoting union,
$\cdot$, denoting concatenation,
$*$, denoting Kleene-Star,
$\lambda$, matching the empty string
and nothing else. Length of a regex is defined as the number of characters from $\Sigma$. ...
13
tl;dr backrefs.
As soon as there is a \1 (or any number that isn't used to escape unicode) in the regexp it is not a regular expression.
Backrefs allows you to match (a+)b\1 which matches n times a followed by b followed by n times a for any n>1. This is not a regular language (it's the poster child of a non regular language).
It is necessary and nearly ...
13
It depends upon whether you've got a regular expression or a regexp: regexps are evil, but regular expressions are a thing of beauty and will never turn evil on you.
By regexp, I mean a modern regular expression: i.e., a regular expression with additional modern features such as backreferences -- e.g., a Perl-compatible regular expression. This is more ...
13
So my question is:
(Why) Is my proof wrong?
If it is right: Why is there no easy way to express permutations?
Your "proof" only looked at permutations of single words, which are finite languages.
Every finite language is regular (e.g. just by listing all of the members with a | inbetween), but there are infinite regular languages (and those ...
12
First off, putting $k$ in the regular expression is not allowed by typical regular expression syntax, unless I'm mistaken. Even adding constant powers is a shorthand notation, not a part of the regular expression formalism. Even if it were possible, using that notation, you could mix $a$s with $b$s, so that not all $a$'s would necessarily come before all $b$...
12
This is some heavy stuff for a high school assignment.
Yuval Filmus's answer is really good, so this is more of a supplementary answer to clarify some of the points he made.
A formal language is a mathematical construction. Their use for programming languages is just one of many possible uses; in fact, linguist Noam Chomsky made significant contributions ...
12
Yep, this is wrong, because of ambiguity.
Consider the following language:
$(a + aa) + a(a + \epsilon)$.
With your method, we see 4 words, $a, aa, aa, a$. But we have duplicates! There are multiple ways to make the same word within the given regular expression.
A better method is to use dynamic programming on an minimal DFA for your language, with no "...
11
First, the string of minimum length might not be defined properly since it might not be unique.
Here is a way to find a string of minimum length:
Convert the regular expression to a nondeterministic finite automaton.
Convert the nondeterministic automaton into a deterministic one.
Use a breadth first search until you encounter the first nonfinal state (if ...
11
Hendrik Jan gives a good answer for complexity class, but not an algorithm itself.
The simplest algorithm to do this that I know of is to convert the regular expression to a DFA. There are known techniques for converting a regular expression to an NFA, and an NFA to a DFA.
Once you have two DFAs, testing for equivalence is efficient and decidable, since ...
11
The set $1^*+0^*$ is composed of two parts: $1^*$ and $0^*$. The first part, $1^*$, is all strings composed entirely of $1$s. The second part, $0^*$, is all strings composed entirely of $0$s. In contrast, $(1+0)^*$ is all strings composed of $0$s and $1$s. Can you now think of a string in $(1+0)^*$ but not in $1^*+0^*$?
11
The problem is NP-hard.
We show this by reducing vertex cover:
Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V'$?
We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows:
All columns, except for the ...
11
A perhaps more interesting question is that of star height. The other answer mentions that if you can't use star, then you can only generate finite languages. What if you are not allowed to nest stars (so something like $(a^*b^*c)^*$ is not allowed)? What if you are only allowed to nest stars two levels deep? $d$ levels deep? It turns out that for every $d$ ...
Only top voted, non community-wiki answers of a minimum length are eligible
