Finite Automata in FASM

Index > DOS > Finite Automata in FASM

Goto page 1, 2, 3, 4 Next

Author

Thread

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 23 Aug 2006, 16:37

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:

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:

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

23 Aug 2006, 16:37

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 23 Aug 2006, 17:12

At least I am very impressed. Very Happy

Very nice!!

23 Aug 2006, 17:12

windwakr

Joined: 30 Jun 2004
Posts: 827

windwakr 23 Aug 2006, 23:06

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

23 Aug 2006, 23:06

Maverick

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

Maverick 24 Aug 2006, 07:58

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

24 Aug 2006, 07:58

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 24 Aug 2006, 09:49

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.

24 Aug 2006, 09:49

donkey7

Joined: 31 Jan 2005
Posts: 127
Location: Poland, Malopolska

donkey7 24 Aug 2006, 18:28

diagram look nicer if numbers are decimal (the 'natural' system):

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:

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

24 Aug 2006, 18:28

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 24 Aug 2006, 19:09

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:

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.

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

24 Aug 2006, 19:09

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 24 Aug 2006, 22:09

ugh... good i am outta university now...

24 Aug 2006, 22:09

okasvi

Joined: 18 Aug 2005
Posts: 382
Location: Finland

okasvi 24 Aug 2006, 22:38

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 |:

24 Aug 2006, 22:38

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 25 Aug 2006, 10:49

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).

Last edited by MHajduk on 26 Oct 2010, 23:46; edited 2 times in total

25 Aug 2006, 10:49

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 25 Aug 2006, 12:12

Very Boring Programmer just showed us a very interesting solutions with FASM - maybe add it to "gems" section !?

25 Aug 2006, 12:12

vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia

vid 25 Aug 2006, 13:10

it is already, since yesterday Razz

25 Aug 2006, 13:10

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 25 Aug 2006, 20:49

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

25 Aug 2006, 20:49

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 26 Aug 2006, 08:33

Madis731:

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

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:

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

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:

and can be described more formally this way:

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

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

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

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}

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:

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

26 Aug 2006, 08:33

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 26 Aug 2006, 14:32

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!

26 Aug 2006, 14:32

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 26 Aug 2006, 16:59

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:

(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

26 Aug 2006, 16:59

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 27 Aug 2006, 17:47

Madis731:

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

(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

27 Aug 2006, 17:47

Madis731

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia

Madis731 27 Aug 2006, 19:28

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

27 Aug 2006, 19:28

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 28 Aug 2006, 14:53

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.

28 Aug 2006, 14:53

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 28 Aug 2006, 16:07

Madis:

I think, that Your automaton is correct, because:

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),
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,
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.

28 Aug 2006, 16:07

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