flat assembler
Message board for the users of flat assembler.

Index > DOS > Finite Automata in FASM

Goto page 1, 2, 3, 4  Next
Author
Thread Post new topic Reply to topic
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Here is an example of finite automaton (i.e. Finite State Machine = FSM), which determines if the binary input sequence (non-empty string built from '0' and '1') represents number divisible by 5.
Code:
; Written in FASM implementation of simple finite automaton, which determines
; if the binary input sequence (non-empty string built from '0' and '1') represents
; number divisible by 5.
;
; Mikolaj Hajduk, 23.08.2006.
;
org     100h

; Mnemonics of the control chars used in program.
;
SPACE   = 20h
TAB     = 09h
CR      = 0Dh           ; Carriage Return
LF      = 0Ah           ; Line Feed

NL      equ CR, LF      ; New line 'char'.

; Macro used to defining a state of an automaton.
;
; Parameters:
; - state name (label),
; - name of the state to which program jumps if actual char is equal to '0',
; - ---------------------------------"--------------------------------- '1',
; - type of the state ('Accept' or 'NotAccept' state) or extra jump if it is
;   start state.
;
macro   State Name, If0, If1, StateType
{
        Name:
                ; Load the next char from the command line.
                ;
                lodsb

                ; Omitting white chars.
                ;
                cmp     al, SPACE
                je      Name
                cmp     al, TAB
                je      Name

                ; Jump in case of end of string.
                ;
                cmp     al, CR
                je      StateType

                ; Jump to the state corresponding to the proper one on the automaton
                ; state diagram.
                ;
                cmp     al, '0'
                je      If0
                cmp     al, '1'
                je      If1

                ; Report an error message in cause of illegal input char.
                ;
                jmp     IllegalChar
}

; Printing macro.
;
macro   Print Str
{
        mov ah, 09h
        mov dx, Str
        int 21h
}

; Address of begin of the command line.
;
mov     si, 81h

; Programming model of an automaton.
;
State   Start,  S0,     S1,     EmptyLine

State   S0,     S0,     S1,     Accept
State   S1,     S10,    S11,    NotAccept
State   S10,    S100,   S0,     NotAccept
State   S11,    S1,     S10,    NotAccept
State   S100,   S11,    S100,   NotAccept

; Reporting proper messages.
;
Accept:
        Print   AcceptedMsg
        jmp     ProgramEnd

NotAccept:
        Print   NotAcceptedMsg
        jmp     ProgramEnd

EmptyLine:
        Print   EmptyLineMsg
        jmp     ProgramEnd

IllegalChar:
        Print   IllegalCharMsg

; End of the program.
;
ProgramEnd:
        mov     ax, 4C00h
        int     21h

; Messages.
;
IllegalCharMsg  db 'Unexpected char in command line.', NL, '$'
EmptyLineMsg    db 'Input sequence should have one char at least.', NL, '$'
AcceptedMsg     db 'Number divisible by 5.', NL, '$'
NotAcceptedMsg  db 'Number indivisible by 5.', NL, '$'
    

State diagram:

Image

Example of use:

Assume that you save above presented code to the file 'FSM.asm' and then compile to 'FSM.com'.

For these exemplary numbers
  • 15 dec = 1111 bin
  • 137 dec = 10001001 bin
  • 5678498 dec = 10101101010010110100010 bin
  • 1555555 dec = 101111011110001100011 bin
you'll obtain:

Image

Regards,
M.H.

[EDIT] Images were moved to another server. [/EDIT]


Last edited by MHajduk on 23 Oct 2010, 17:19; edited 3 times in total
Post 23 Aug 2006, 16:37
View user's profile Send private message Visit poster's website Reply with quote
LocoDelAssembly
Your code has a bug


Joined: 06 May 2005
Posts: 4633
Location: Argentina
LocoDelAssembly
At least I am very impressed. Very Happy

Very nice!!
Post 23 Aug 2006, 17:12
View user's profile Send private message Reply with quote
windwakr



Joined: 30 Jun 2004
Posts: 827
Location: Michigan, USA
windwakr
Wow. It looks too simple to do something like that.

I have 2 questions:

1. How exactly does it figure out if number is divisible by 5

2. Can it be modified for other numbers (like 4 or 3),if so how?

_________________
----> * <---- My star, won HERE
Post 23 Aug 2006, 23:06
View user's profile Send private message Reply with quote
Maverick



Joined: 07 Aug 2006
Posts: 251
Location: Citizen of the Universe
Maverick
Hi windwakr:

Look for Mealy and Moore state machines, for example here:
http://en.wikipedia.org/wiki/Finite_state_machine

BTW: divisible by 4 is as easy as it could be: it's sufficient that the two least significant bits are 0.

PS:

MHajduk: nice work. Smile

Thomasz: very nice preprocessor indeed. Wink
Post 24 Aug 2006, 07:58
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
locodelassembly:
Muchas gracias HernĂ¡n! Very Happy

windwakr:
Thank You. Smile

Ad. 1. Give me some time; I'll present sketch proof of correctness of this construction.
Ad. 2. Yes, it is possible for every number. But, unfortunately, there doesn't exist finite automaton for determining if number is prime or not... Sad

Maverick:
Thanks. Smile

Generally: number is divisible by 2^n, if last n bits are equal to 0.

Regards,
M.H.
Post 24 Aug 2006, 09:49
View user's profile Send private message Visit poster's website Reply with quote
donkey7



Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska
donkey7
diagram look nicer if numbers are decimal (the 'natural' system):
Image

in general (if n id the divisor and k is number base of input number):
- there are n states - from 0 to n-1
- each state has k 'outcoming connections' (i don't know how they are named),
- total number of 'incoming connections' is n*k (as you can alculate from above two points),

in following diagram:
Image
b is caclulated as: b = ((a * k) + i) mod n

in first example we have k= 2 (binary system) and n= 5 (divisor)

hope i'm correct Smile
Post 24 Aug 2006, 18:28
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
donkey7:
Yes, You are right. Below I show proof for number system with base equal to 2 (i.e. binary system).

windwakr:
Here is an example of automaton, which determines if given sequence of chars '0' and '1' represents a number divisible by 3.


State diagram:

Image

Core of the code:
Code:
; Programming model of an automaton.
;
State   Start,  S0,     S1,     EmptyLine

State   S0,     S0,     S1,     Accept
State   S1,     S10,    S0,     NotAccept
State   S10,    S1,     S10,    NotAccept    


Notice that:

  • For every automaton, which determines divisibility by n, n+1 states (start state and n states corresponding to all rests from division modulo n) would be completely enough.

  • Program doesn't execute any division, therefore it is independent of architecture of processor. We can test very large numbers. We have a "supercomputer" under old, good DOS. Wink


Regards,
M.H.

[EDIT] Images were moved to another server. [/EDIT]


Last edited by MHajduk on 23 Oct 2010, 21:24; edited 3 times in total
Post 24 Aug 2006, 19:09
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
ugh... good i am outta university now...
Post 24 Aug 2006, 22:09
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
okasvi



Joined: 18 Aug 2005
Posts: 382
Location: Finland
okasvi
vid wrote:
ugh... good i am outta university now...


heh, I'm happy that I havent gone to any Razz

*waiting for post by Tomasz*

_________________
When We Ride On Our Enemies
support reverse smileys |:
Post 24 Aug 2006, 22:38
View user's profile Send private message MSN Messenger Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Here you have a proof of the correctness of the mentioned automata construction. Since there are many formulas and this forum doesn't allow proper formatting for mathematical texts whole proof was written using LaTeX and attached below (in the form of images).

Image

Image


Last edited by MHajduk on 26 Oct 2010, 23:46; edited 2 times in total
Post 25 Aug 2006, 10:49
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Very Boring Programmer just showed us a very interesting solutions with FASM - maybe add it to "gems" section !?
Post 25 Aug 2006, 12:12
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
it is already, since yesterday Razz
Post 25 Aug 2006, 13:10
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Heh, I tried and I tried and I.....failed Sad
http://board.flatassembler.net/topic.php?t=4731
Its very difficult to do something like this with NN. That's a totally different thing Razz
I thought about it for a very long time and I realized that neurons don't know their "state" at all times so I need to connect the "generator" to all the neurons and then I need to have AND gates between them and it would become too complicated...

...btw, the states don't need to be linearly connected to the number you are testing. For example when you know how to divide by 2 and 3 then you can combine these.
EDIT: I couldn't find one for 6, but I know there's one shortcut for example with power of 2's like you have mentioned. The machine just sits in a state and waits for zeros. Then it starts moving towards its goal. Any "1" gathered on the way puts it to the first state. It can be done with n+2 states where n is not the number, but base to logarithm of a power of 2 number: 2^n


Last edited by Madis731 on 26 Aug 2006, 14:33; edited 1 time in total
Post 25 Aug 2006, 20:49
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Madis731:

To realize XOR function with NN You don't need float weights:

Image

Fact:
Single neural cell with n inputs using presynaptic inhibition mechanism can execute every logical function of n arguments.


For all those who aren't familiar with neural networks I wish to present a short description of the simplest mathematical model of the artificial neuron. All examples of the neural cells presented by me in this thread follow this basic description.


Artificial neuron with n+1 inputs usually depicted graphically this way:

Image

is described as a function of n+1 binary arguments and defined as follows:

Image

where w0, w1, ..., wn are some constants called weights and t is a number called threshold.

Using the above presented model of the artificial neuron is enough for simulations of the simple logical functions but, unfortunately, some of them (like XOR, for example) can't be performed by a single neural cell.

As we will see it further, simple modification of the aforementioned mathematical model solves this problem completely.

Presynaptic inhibition is a process of blocking signals incoming through the synapse a by the signal incoming through the synapse b what is usually depicted graphically as follows:

Image

and can be described more formally this way:

Image

in a more condensed form: c = a*(1 - b).

Mechanism of the presynaptic inhibition can be generalized to the cases when synapse xk, where k ∈ {0, 1, ..., n}, is inhibited by synapses xj, where j ∈ Jk and Jk is a some subset of the set {0, 1, ..., n}.

We define sk as a product

Image

Then our mathematical model of the artificial neuron can be extended on the cases with presynaptic inhibition this way:

Image

Having this generalized description we can explain why the neural cell presented above, on the beginning of this post, realizes XOR operation on the two given binary arguments.

Function associated with this neuron

Image

can be simplified accordingly to the obvious fact that a(1 - b) + b(1 - a) can be either 0 or 1 for a, b ∈ {0, 1}

Image

i.e. y = a(1 - b) + b(1 - a).

It's evident that XOR(a, b) = a(1 - b) + b(1 - a), because for all a, b ∈ {0, 1} both sides of this equation are identical:

Image

so we have y = XOR(a, b) that which was to be demonstrated.


Last edited by MHajduk on 26 Oct 2010, 20:05; edited 3 times in total
Post 26 Aug 2006, 08:33
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Strangely I haven't read about presynaptic braking, I guess I've missed that. If that is the case, then modifying the NN code, I could do automata in NN!? I based this belief on the second part of your sentence: "every logical function of n arguments". Its that I'm only afraid that it doesn't classify as NN if it uses structures like transistor (C-B-E) current blocking and allowing ^o)
Anyway, thanks!
Post 26 Aug 2006, 14:32
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Madis731:

Instead 'presynaptic braking' should be 'presynaptic inhibition' (I tried to translate this term from Polish - that explains my mistake). Anyway, it's the same idea.

Presynaptic inhibition really exists in the nature:

Image

(picture is taken from Debasis Pramanik, M.D., "Principles of physiology").

Regards,
M.H.

[EDIT] Image was moved to another server. [/EDIT]


Last edited by MHajduk on 21 Oct 2010, 17:05; edited 2 times in total
Post 26 Aug 2006, 16:59
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Madis731:

This is a state diagram for an automaton, which checks divisibility by 6:

Image

(notice some kind of specific "symmetry" of this automaton).

Here You have core of the code:
Code:
; Programming model of an automaton.
;
State   Start,  S0,     S1,     EmptyLine

State   S0,     S0,     S1,     Accept
State   S1,     S10,    S11,    NotAccept
State   S10,    S100,   S101,   NotAccept

State   S11,    S0,     S1,     NotAccept
State   S100,   S10,    S11,    NotAccept
State   S101,   S100,   S101,   NotAccept    


Regards,
M.H.

[EDIT] Image was moved to another server. [/EDIT]


Last edited by MHajduk on 21 Oct 2010, 23:30; edited 2 times in total
Post 27 Aug 2006, 17:47
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2141
Location: Estonia
Madis731
Hmm, I hope I did it correct - I only tested it in my head:
http://enos.itcollege.ee/~mkalme/PAHN/Automata/
There are PNG and SVG variants of it. It uses the /3 automata and makes use of the binary SHR /2. I didn't think much about naming conventions Sad
Post 27 Aug 2006, 19:28
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Madis731:
It seems, that our automata are functionally equivalent, but Yours is better, because it has less states (5 instead 7). Smile

Regards,
M.H.
Post 28 Aug 2006, 14:53
View user's profile Send private message Visit poster's website Reply with quote
MHajduk



Joined: 30 Mar 2006
Posts: 6034
Location: Poland
MHajduk
Madis:

I think, that Your automaton is correct, because:
  1. You first check if just read binary input is divisible by 3 and wait in "2*" state, which we can name "quasi-accepting" (rest of dividing modulo 3 is equal to 0),
  2. if the next char is '0' we are happy, because just read number is divisible by 2 (and consequently by 6); we go to "0" state,
  3. if the next char is '1' we migrate from "quasi-accepting" state to "1", because the rest mod 2 (and mod 3 too) is equal to 1.
etc. until the end of the sequence.

Regards,
M.H.
Post 28 Aug 2006, 16:07
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2, 3, 4  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.