# Matches -\> regexp?

**URL:** <https://www.ruby-forum.com/t/matches-regexp/53201>\
**Category:** Ruby\
**Created:** [December 12, 2005, 9:34pm UTC](https://www.ruby-forum.com/t/matches-regexp/53201 "2005-12-12T21:34:39Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![akoSS](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/47e85d/32.png) [@akoSS](https://www.ruby-forum.com/u/akoSS)\
**Post date:** [December 12, 2005, 9:34pm UTC](https://www.ruby-forum.com/t/matches-regexp/53201/1 "2005-12-12T21:34:39Z")

</div>

Hello,

this is not exactly a ruby problem, i hope people will not consider  
this spamming.

does anyone know of any reference or an algorithm to build a regular  
expression (a finite automaton, in general) that would match a given  
set of strings? i of course mean a regexp that would match just the  
given strings, and not any other. so solutions like /^.\*$/ are not  
acceptable 😉

thanks  
konstantin

---

<div class="post-metadata">

**Author:** ![akoSS](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/47e85d/32.png) [@akoSS](https://www.ruby-forum.com/u/akoSS)\
**Post date:** [December 12, 2005, 9:37pm UTC](https://www.ruby-forum.com/t/matches-regexp/53201/2 "2005-12-12T21:37:39Z")

</div>

ako… schrieb:

> thanks  
> konstantin

nice challenge, reminds me a bit of the 4th rubyquiz :\>

---

<div class="post-metadata">

**Author:** ![akoSS](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/47e85d/32.png) [@akoSS](https://www.ruby-forum.com/u/akoSS)\
**Post date:** [December 12, 2005, 9:52pm UTC](https://www.ruby-forum.com/t/matches-regexp/53201/3 "2005-12-12T21:52:41Z")

</div>

> ako… schrieb:
> 
> > does anyone know of any reference or an algorithm to build a regular  
> > expression (a finite automaton, in general) that would match a given  
> > set of strings? i of course mean a regexp that would match just the  
> > given strings, and not any other. so solutions like /^.\*$/ are not  
> > acceptable 😉

This is essentially an information compression problem. There’s  
always a trivial solution:

s = %w{find only these strings}  
r = Regexp.new(s.map {|w| ‘\A’ + w + ‘\Z’}.join(’|’))

The _real_ problem is finding the shortest possible regexp. 😉

---

<div class="post-metadata">

**Author:** ![akoSS](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/47e85d/32.png) [@akoSS](https://www.ruby-forum.com/u/akoSS)\
**Post date:** [December 12, 2005, 9:58pm UTC](https://www.ruby-forum.com/t/matches-regexp/53201/4 "2005-12-12T21:58:43Z")

</div>

well, right, that is what i mean.

---

<div class="post-metadata">

**Author:** ![akoSS](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/47e85d/32.png) [@akoSS](https://www.ruby-forum.com/u/akoSS)\
**Post date:** [December 12, 2005, 10:04pm UTC](https://www.ruby-forum.com/t/matches-regexp/53201/5 "2005-12-12T22:04:43Z")

</div>

i suspect that from your trivial solution we can arrive at the final  
solution by just performing a DFA minimization. the same thing that lex  
and yacc do when they generate code. so i guess i have answered my own  
question. thanks for helping me. your trivial solution just made my  
brain work.

konstantin

---

<div class="post-metadata">

**Author:** ![akoSS](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/47e85d/32.png) [@akoSS](https://www.ruby-forum.com/u/akoSS)\
**Post date:** [December 13, 2005, 2:19pm UTC](https://www.ruby-forum.com/t/matches-regexp/53201/6 "2005-12-13T14:19:29Z")

</div>

ako… wrote:

> i suspect that from your trivial solution we can arrive at the final  
> solution by just performing a DFA minimization. the same thing that  
> lex and yacc do when they generate code. so i guess i have answered  
> my own question. thanks for helping me. your trivial solution just  
> made my brain work.

Another option is to build up a tree and create the RX from that. I  
once  
wrote that:

14:12:23 [c]: ( echo foo; echo bar; echo band ) | create-rx.rb  
(?:ba(?:nd|r)|foo)

Kind regards

```
robert
```