Finite Automatons and images

At a lecture about regular expressions and automatons, we were introduced to the posibility of using automatons to compress images. During the course we have worked with a java package for automatons, so i made a quick hack to render regexps as images.

The concept is that every acepting state represents black area, and and using a recursive definition of the areas.

area

Here is the area for the string “031”

Using this recursive definition it is posible to adress alle aereas, well in reality I choose a “resolution” and using strings upto a certeain length. I generate all the strings and check whether they are accepted, and should be colored.

A couple of examples.

  • regexppicure
  • regexppicure2
  • regexppicure3

The hack I used to make the images above (regexp_picture_render), you need the dRegAut packackage thou it might work with this (http://www.brics.dk/automaton/)

Here is a few regexps to try out, some are more interesting than others…

  • (1+0+2+3)*(30+03+12+21)
  • (0+1+2+3)*(22+11+00+33)(1+2)
  • (0+1+2+3)*(33+00)(1+2+3+0)*(0+3)
  • (1+2+3)*03(1+2)
  • ((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*)
  • (((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*))(1+2+3)*(1+2)
  • (((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*))(1+2)(1+2+3+0)*(0+3)
  • (((0+1+2+3)*(12+21))+((03+30)(0+1+2+3)*))(1+2+3)*03(1+2)
  • (((0+1+2+3)*(2+1))+((2+1)(0+1+2+3)*))(1+2+3+0)*0(1+2)
  • (((0+1+2+3)*(2+1))+((2+1)(0+1+2+3)*))(1+2+3+0)*3(0+3)
  • (1+2+3+0)*(1+2)(0+3)(1+2)
  • (1+2+3+0)*(1+2)(0+3)(1+2)

Leave a Reply