understanding regular expressions to finite state machines

i recently came across a question on designing a state machine for detecting a binary string sequence. the solution to such a problem has two approaches. the very commonly followed approach is analyze the "given" sequence over and over again and try to scribble state transitions and test the patterns on it to check if breaks. i believe this is the way hardware engineers work this out, primarily because they spend some time which is considerably less than what they spend for other problems they analyze :) i say hi to "theory of relativity" here..

the second approach is to have rules to analyze such problems because they only consist of binary patterns (0s and 1s) and a rule based solution is like some kind of a program, so you don't necessarily have to do much testing or alter, adjust your state machine as you try to solve the problem. the theory that deals with such kind of problems of pattern matching and sequence detection is the famous regular expression or the re. regular expressions can be analyzed as finite automata, or what can be called as our commonly known finite state machine.

so the best way to deal with such problems is to represent the sequence as a regular expression and just try converting it to finite state machine based on rules.

So some notations wrt re:

a* : an a* would mean 0 or more matches of the letter "a" followed by successive letters. for instance a*b matches "ab", "aab", "aaab" or just "b".

a+ : an a+ would mean 1 or more matches of the letter "a" followed by successive letters. for instance a+b matches "ab", "aab", "aaaab" but will not match just b.

a? : an a? would mean 0 or 1 matches of the letter "a" followed by successive letters. for instance a?b matches "ab" or just "b" but will not match "aaab".

the problem statement mentioned the sequence detection for the string 101011, which also meant that the state machine should be able to sustain 101010111 or a 111101011 as a match since both these string involve the string 101011.

Looking more closely at the sequence, a few points to notice.

a. match as many 1s preceeding this sequence so that we end up matching  11101011, or 11111111010111 or 11111111111111101011. to put this in the basic atom terminology, we match (1+)01011. 

b. match as many 10s preceeding this sequence so that we end up matching 10101011 or 101010101011 ... so we can end up consuming any number of 10s once we get past the first occurrence of 10. to put this in the basic atom terminology, we match (1+)0(10)+11

so that is pretty much translating problem into a regex string. The following slideslow will try to illustrate a method to translate a regular expression into a statemachine. There might have been mistakes in my understanding and representation. Comment or e-mail me if you think there is something wrongly interpreted.

Regular Expression to Finite State Machine

Thanks

Shyam

gmail integration with emacs

I think it is fun to have Emacs act as your mail client. It's like when u are busy writing code, and you got to send in some snippets or a quick mail on the issue, you just don't leave the editor!. So here is how you integrate Emacs to access your Gmail compose. Note, your mails sent from Emacs are also stores in the "sent" label on your Gmail!

pre-requisites

1. emacs 23.2
   Use the latest version of emacs, I used emacs23.2 while i made the customization.
   
   download emacs from http://ftp.gnu.org/gnu/emacs/
   
2. gnutls
   gnutls is the gnu transport layer security library which ensures secure client/server communication over the transport layer.
   
   http://www.gnu.org/software/gnutls/gnutls.html for more info on gnutls
    
3. Libgcrypt
   To build gnutls, this package may be required it is provided in the gnutls download link along with gnu tls. One might have to download it separately.

The .authifo File

1. The authinfo file stores the login information for the mail account. Create the .authinfo file
    
2. Insert the following line into the .authinfo file which u can create and place in the ~/. directory
   
   machine smtp.gmail.com login @gmail.com password
    
3. Modify the permissions of the .authinfo file as follows
   
   chmod go-rwx .authinfo
   chmod u+rw .authinfo

Emacs Init Config (.emacs)

Add this section to your .emacs

;; email setting for my emac
(setq send-mail-function 'smtpmail-send-it
message-send-mail-function 'smtpmail-send-it
smtpmail-starttls-credentials
'(("smtp.gmail.com" 587 nil nil))
smtpmail-auth-credentials
(expand-file-name "~/.authinfo")
smtpmail-default-smtp-server "smtp.gmail.com"
smtpmail-smtp-server "smtp.gmail.com"
smtpmail-smtp-service 587
smtpmail-debug-info t)

Sending mail
The keybinding for emacs to send mail is

1. C-x m to compose mail 
2. C-c C-c to send mail when you are done composing the mails
   

Thanks

Shyam

timescale in verilog

The timescale directive in Verilog used to model hardware is quite confusing, most people I have interacted with most times do not understand or are just ignorant of the timescale directive. So I thought I should jot this one down so that next time I meet up with people ignorant of this, I can point them to this post!

The directive is used to model delays in signal assertions with specific precision. Unlike vhdl, which has specific time unit constructs [ns(nanosecond), ps(picosecond), ms(millisecond)] Verilog inherently does NOT support these data-types and hence there is no time unit. The unit and the precision is specified using the timescale directive.

Aan example Verilog codes would feature this directive as
`timescale 1ns/100ps
which is in the format `timescale time_units / time_precision

  A#100 in verilog is used to identify 100 units of time. For instance, with a `timescale of 1ns/100ps

  Avalue of #21.375 is indicated as

21.375 * 1 ns = 21.375 ns and the .375 is rounded off to the next 100ps ~ 400ps.

so #21.375 is taken as 21.4ns

If the timescale is set to 1ns / 10ps, the precision is higher and so the math is 21.375 * 1ns = 21.375 and then the .375 is rounded to the next 10th pico second which is 380 ps

So a #21.375 ~ 21.380 ps in this case.

--
shyam

counting squares contd...

As a continuation of the previous post on counting squares, here is the update. Only two of my friends commented their solutions to this simple problem and here are two approaches.

lets assume a board where n = 6. drawing a line would make the board look like this.

   +----+----+----+----+----+----+
   | \\ |    |    |    |    |    |
   +----+----+----+----+----+----+
   |    | \\ |    |    |    |    |
   +----+----+----+----+----+----+
   |    |    | \\ |    |    |    |
   +----+----+----+----+----+----+
   |    |    |    | \\ |    |    |
   +----+----+----+----+----+----+
   |    |    |    |    | \\ |    |
   +----+----+----+----+----+----+
   |    |    |    |    |    | \\ |
   +----+----+----+----+----+----+

what i think is the the "indian" geeky way of looking at it is to eliminate the  other half and visualize the same board as

   +----+
   | \\ | number of squares = 1
   +----+----+
   |    | \\ | number of squares = 2
   +----+----+----+
   |    |    | \\ | number of squares = 3
   +----+----+----+----+
   |    |    |    | \\ | number of squares = 4
   +----+----+----+----+----+
   |    |    |    |    | \\ | number of squares = 5
   +----+----+----+----+----+----+
   |    |    |    |    |    | \\ | number of squares = 6
   +----+----+----+----+----+----+

and so people arrive with the standard n(n+1)/2 which people remember, thanks to the caning by their high school math teacher for not remembering the sum of natural numbers series up to n :)

but there is a simple way of looking at it
1. the number of squares slashed by the diagonal is n.
2. total number of squares = n^2
3. so remaining squares = (n^2) - n which is equally divided between the two halves
4. so total squares not slashed = [(n^2) - n] / 2 = M
5. so if you want to include the number of squares slashed by the diagonal as
well, then its M + n

I took the first way to get the equation, but that is probably the harder way to do math. a thoughtful layman would come up with the second method first time and is backed by observation.
 
Cheers
Ghanashyam

counting squares

While in the midst of trying to solve a problem, a question just struck to me. Suppose if there is a chess board of n checks [the normal chess board has 8x8 so n=8], and you draw a diagonal across the entire board from one edge to the other edge, what is the equation that can give us the number of squares in the chess board on one side of the diagonal? Squares include those across which the diagonal has been drawn. for instance if a diagonal is drawn across a board with n=4, then the number is 10.

I spent a couple of minutes of thought on how to fit an equation into this but I thought I should have got it faster. There is one approach I followed.. let me know what approach you guys follow!


Cheers

Ghanashyam

walk to remember...

what other place than an oceanside to experience serenity.

along the shores,
the waters in an endless effort,
to kiss away the sands at your feet,
the rhythmic sounds of waves,
in resonance with breezing winds,
sing adieu to a beautiful, smiling and dying sun.

it gives you the just-enough-silence,
it shows you how much you just don't matter,
it shows you its might,
it shows you its magnanimity,
it shows you how time is prolonged,
it shows you how enormously long a minute is.

it is a serene experience. i wait to find an experience more blissful than at the one at the sea. it is a walk to remember...


cheers
shyam

quick .emacs access

when one talks about emacs customization, most of it is going to be editing the .emacs, which is the init file of emacs. emacs loads the init file, by default, stored at the $HOME or the ~/. location in your system. Some times one never knows which is the .emacs that our emacs is using typically when one has been updating his emacs through different versions. the easiest way to find out where your .emacs is to do a C-x C-f ~/.emacs RET  

for frequent .emacs users, typing C-x C-f ~/.emacs is also tiring, or basically you might say its redundant. once a .emacs is edited, one has to load it again to see the change effects. to make it a quick access, you could just create a function which opens a .emacs if not open and loads it if its already open. a keybinding proves very convenient and here is what you add in your .emacs.



(defun open-load-init-emacs ()

"function to open the .emacs in lisp mode and load it"

    (interactive);; function be called interactively

    (if (equal (buffer-name) ".emacs")

         (eval-buffer) ;; if open, evaluate buffer or load it

         (progn (find-file "~/.emacs") (eval-buffer))

    )

    ;; the progn creates a body of commandsfind .emacs, load it

    (lisp-mode) ;; enable lisp mode)
(global-set-key "\C-x." 'open-load-init-emacs) ;; set the key binding to C-x.

cheers
shyam



git quick start guide

I can almost certainly assert that Emacs has been the best piece of open source software, for that matter, the best software I have ever used. The reasons are simple. Emacs in itself is simple, it just does the jobs right, it isn't troublesome. Some one somewhere has foreseen things which you would want in an editor and when you look out for that one thing you miss badly, you find it and it works awesome. Alongside Emacs, I started using this piece of open source software git.

Git is a version control software tool and was implemented by Linus Torvalds. I must say git has been as wonderful as software as emacs. My tryst with version control starts from using a commercial  Clearcase to an open source CVS, to a seemingly meaningless SVN to an ideal tool git. Apparently, any piece of open source software is almost always written by geeks for geeks and there is a lot of "meaningful" documentation underneath. And for many of the "just-get-the-job-done" people, I  think, this is the crux of the problem. There is no "next-click-next-click" tool flow. We all grew up playing "space commander" on "windows" you see.

To make things easier, to get as many people use git instead of svn, I thought, I should list down a quick start guide to moving from svn to git. There are numerous amounts of git tutorials on the net which are far more detailed and far more interesting. So this is by no means undermining the effectiveness and the content of all such documentation. This is not a detailed user guide, it's just a quick start guide, which lets you start with changing things.

Read on. https://docs.google.com/View?id=dkcpzd9_10cgjbpbfj

Cheers 

Ghanashyam

a weekend sketch...

I found some good time to spend this weekend. while am not at work, one of the things I would normally "like" to do is sketching. I am not that good a creative artist, though, I am just amazed by how beautiful women are. They are perfect, physically and in human nature. One can just wonder in awe as to how beautiful a woman is. She's got those prettiest pair of eyes in the universe, she s got those curves which you always crave to feel, she s got those mellifluous voice you just can't stop imagining, she s got the tender slender gait which you cannot stop staring at... she is beautiful. If there exists a god, he must have had an incredibly awesome experience creating a woman. One way to get the experience is to sketch it out.. and here is the result of some good time I spent. The aim is to get it right by trying over and over again as the so called god got it first time...

cheers
Ghanashyam

time stamping with org-mode calendar

org mode in emacs has this wonderful feature of integrating the calendar in itself. A C-c . key binding in org mode invokes the calendar. you can move around dates with the S- ->(shift right arrow: forward day) and S-<-(shift left arrow: backward day). but this is only in an org-mode buffer, buffers which have a .org extension or buffers where you manually switch on org-mode by M-x org-mode RET.

one can enable this on all types of buffers globally. put this in to your .emacs

(global-set-key "\C-c." 'org-time-stamp)

so in any buffer, one can C-c . to get in a date time stamp.

cheers!

shyam