flat assembler
Message board for the users of flat assembler.
Index
> DOS > Finite Automata in FASM Goto page 1, 2, 3, 4 Next 
Author 

LocoDelAssembly 23 Aug 2006, 17:12
At least I am very impressed.
Very nice!! 

23 Aug 2006, 17:12 

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? 

23 Aug 2006, 23:06 

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. Thomasz: very nice preprocessor indeed. 

24 Aug 2006, 07:58 

MHajduk 24 Aug 2006, 09:49
locodelassembly:
Muchas gracias HernĂ¡n! windwakr: Thank You. 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... Maverick: Thanks. Generally: number is divisible by 2^n, if last n bits are equal to 0. Regards, M.H. 

24 Aug 2006, 09:49 

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

24 Aug 2006, 18:28 

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:
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 24 Aug 2006, 22:09
ugh... good i am outta university now...


24 Aug 2006, 22:09 

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 *waiting for post by Tomasz* _________________ When We Ride On Our Enemies support reverse smileys : 

24 Aug 2006, 22:38 

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 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 25 Aug 2006, 13:10
it is already, since yesterday


25 Aug 2006, 13:10 

Madis731 25 Aug 2006, 20:49
Heh, I tried and I tried and I.....failed
http://board.flatassembler.net/topic.php?t=4731 Its very difficult to do something like this with NN. That's a totally different thing 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 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 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 (CBE) current blocking and allowing ^o)
Anyway, thanks! 

26 Aug 2006, 14:32 

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

27 Aug 2006, 19:28 

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). Regards, M.H. 

28 Aug 2006, 14:53 

MHajduk 28 Aug 2006, 16:07
Madis:
I think, that Your automaton is correct, because:
Regards, M.H. 

28 Aug 2006, 16:07 

Goto page 1, 2, 3, 4 Next < Last Thread  Next Thread > 
Forum Rules:

Copyright © 19992023, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.
Website powered by rwasa.