Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <blockquote> <p>I'm wondering how to find a set of all matches to a given regex with a finite number of matches.</p> </blockquote> <p>Because you're only considering regular expressions denoting <em>finite</em> languages, you're <em>actually</em> considering a subset of the regular expressions over an alphabet. In particular, you're not dealing with regular expressions constructed using the Kleene star operator. This suggests a simple recursive algorithm for constructing the set of strings denoted by the regular expressions without Kleene star over an alphabet Σ.</p> <pre><code>LANG(a) = {a} for all a ∈ Σ LANG(x ∪ y) = LANG(x) ∪ LANG(y) LANG(xy) = {vw : v ∈ LANG(x) ∧ w ∈ LANG(y)} </code></pre> <p>Consider a regular expression such as <code>a(b ∪ c)d</code>. This is precisely the structure of your cats and dogs example. Executing the algorithm will correctly determine the language denoted by the regular expression:</p> <pre><code>LANG(a((b ∪ c)d)) = {xy : x ∈ LANG(a) ∧ y ∈ LANG((b ∪ c)d)} = {xy : x ∈ {a} ∧ y ∈ {vw : v ∈ LANG(b ∪ c) ∧ w ∈ LANG{d}}} = {ay : y ∈ {vw : v ∈ (LANG(b) ∪ LANG(c)) ∧ w ∈ {d}}} = {ay : y ∈ {vd : v ∈ {b} ∪ {c}} = {ay : y ∈ {vd : v ∈ {b,c}}} = {ay : y ∈ {bd, cd}} = {abd, acd} </code></pre> <p>You also ask whether there is an algorithm that determines whether a regular language is finite. The algorithm consists in constructing the deterministic finite automaton accepting the language, then determining whether the transition graph contains a walk from the start state to a final state containing a cycle. Note that the subset of regular expressions constructed without Kleene star denote finite languages. Because the union and concatenation of finite sets is finite, this follows by easy induction.</p>
    singulars
    1. This table or related slice is empty.
    1. POCreate set of all possible matches for a given regex
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USdanportin
    1. USdanportin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COGood answer, but you might want to clarify what you mean by "checking for cycles". Certainly the graph of a DFA containing a cycle is necessary for the language it accepts to be infinite, but it is not sufficient.
      singulars
      1. PO
      1. USPatrick87
    2. COYou're right. I changed "checking for cycles" to "determining whether there is a walk from the start state to a final state containing a cycle." The latter is a sufficient condition, the former merely necessary. Thanks.
      singulars
      1. PO
      1. USdanportin
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload