#finite automata

[juh-wasnt-deactivated19691231]

seeking guidance on FSM implementation for FRC robotics, an application which has some properties to it:

Transitions between nominal states may take several seconds

Transitions may be interrupted/hijacked/aborted/cancelled

I’m comfortable with the general idea of finite automata, but I’m not very experienced with implementation of a lot of things. We tried a big enum with pairs of $state and moving_to_$state, but this became unwieldy and difficult to adapt to manual control scenarios. If this tale inspires you, I’m all ears

[1ucasvb]

Animation I've done for explaining part of my research.

[spookfished]

clutching my head theory of computation

[cetaceanhandiwork]

the conversation around generative neural networks is a dumpster fire in a dozen different ways but I think the part that disproportionately frustrates me, like on an irrational pet peeve level, is that nobody in that conversation seems to understand automata theory

back before most of these deep learning techniques were a twinkle in a theorist's eye, back when computing was a lot less engineering and a lot more math, computer scientists had worked out the math of different "classes" of computer system and what kinds of problems they could and couldn't solve

these aren't arbitrary classifications like most taxonomy turns out to be. there's qualitative differences. you can draw hard lines: "it takes class X or above to run programs with Y trait", and "only class X programs or below are guaranteed to have Y trait". and all of those lines have been mathematically proven; if you ever found a counterexample, then we'd be in "math is a lot of bunk" territory and we'd have way bigger things to worry about

this has nothing to do with how fast/slow the computer system goes; it's about "what kinds of program can it run at all". so it includes emulation and such. you can emulate a lower system in a higher one, but not vice versa

at the top of this heap is turing machines, which includes most computers we'd bother to build. there's a lot of programs that it's been mathematically proven require at least a turing machine to run. and this class of programs includes a lot of things that humans can do, too

but with this power comes some inevitable restrictions. for example, if you feed a program to a turing machine, there's no way to guarantee that the program will finish; it might get stuck somewhere and loop forever. in fact there's some programs that you straight up can't predict whether they'll ever finish even if you're looking at the code yourself

these two are intrinsically linked. if your program solves a turing complete problem, it needs a turing machine; nothing less will do. and a turing machine is capable of running all such programs, given enough time.

ok. great. what does any of that jargon have to do with AI?

well... the important thing to know is that the machine learning models we're using right now can't loop forever. if they could loop forever they couldn't be trained. for any given input, they'll produce an output in finite time

which means... well, any program that requires a turing machine to run, or even requires a push-down automaton to run (a weaker type of computer system that can get into infinite loops but that you can at least check ahead of time if a program will get stuck or not), can't be emulated by these systems. they've got to be in the next category down: finite state machines at most - and thus unable to compute, or emulate computation of, programs that inhabit a higher tier

and there is a heck of a lot of stuff we conceptualize as "thinking" that doesn't fit in a finite state machine

...I suspect it will some day be possible for a computer program to be a person. I am absolutely certain that when that day comes, the computer program who's a person would require at least a turing machine to run them

what we have right now isn't that. what we have right now is eye spots on moths, bee orchids, mockingbirds. it might be "artificial intelligence", depending on your definition of "intelligence", but prompt it to do things that we've proven only a turing machine can do, and it will fall over

and the reason I consider this an "irrational pet peeve" and not something more severe? is because this information doesn't actually help solve policy questions! if this is a tool, then we still need to decide how we're going to allow such tools to be built, and used. it's not as simple as a blanket ban, and it's not as simple as letting the output of GNNs fully launder the input, because either of those "simple" solutions are rife for abuse

but I can't help but feel like the conversation is in part held back by specious "is a GNN a people" arguments on the one hand, and "can a GNN actually replace writers, or is it just fooling execs into thinking it can" arguments on the other, when the answer to both seems to me like it was solved 40 years ago

[bruoche]

Finite State Automata defining spell syntax.

The spells use only three different characters to be written, "╭" (which can represent "0"), "ʌ" (which can represent "1") and a validation symbol "ᴎ" that can represent ";". When writing spells, spaces, indentation and parenthesis can be added to make them more readable. Those do not modify the spell meaning as only the three characters precedently mentionned matter.

A fourth glyph "╰" can be placed to signify the begining of a spell too, so indentations are more logical, but this character do not add meaning to the spell either.

This automaton is nearly deterministic, with the exception of the validating "root" state, that can only go back on itself to exit the current loop (an ongoing while, the spell itself or a function definition for exemple). The spell also cannot validate before exiting every ongoing loop, and can only validate once every loop are exited. Otherwise, the rest of the states and their transitions are entirely deterministic.

A more detailed version of the FSA :

[erstwhilesparrow]

tagged by @boatemlag

Are you named after anyone? my legal name is from a character in a sitcom my dad likes. this fact makes me feel justified in disliking it. the name sparrow is from . the real life birds. due to how i like birds and i think it is good to model my online behaviour off small flightly unremarkable little critters

When was the last time you cried? ahahaha. the time around midnight between wednesday may 28 and thursday may 29.

Do you have kids? nope!

Do you use sarcasm a lot? no idea what would count as 'a lot', this is not something i pay much attention to. i imagine i must, or else i wouldn't be constantly telling myself to make an effort toward sincerity?

What sports do you play? none!

What's the first thing you notice about people? clothes? i have to imagine? or faces?

What's your eyecolor? black? dark brown? one of those

Scary movies or happy endings? scary movies :] i love to be upset and afraid. and also i get to go "SEE? MY FEAR OF EVERYTHING ALL THE TIME IS ACTUALLY CORRECT AND ADAPTIVE." except the movie is fiction so i'm still wrong.

Any special talents? none that come to mind. i've really got nothing going on :P

What are your hobbies? writing! theoretically reading but in my head that has become part of writing in that it's part of the necessary [resting and gathering inspiration] phase of writing. i don't exactly "go" "bird-watching" but i like going to local parks and looking/listening for birds as i stroll

Do you have pets? nope! not really the space (or the people willing to make space) for it

How tall are you? 169 cm. i could round up and i wouldn't be surprised if i was 170 cm but then i don't get to say 69, so. anyway. i'm not checking how much that is in feet.

Favorite subject in school? in high school i suspect it was physics or math. in university it was definitely history though i was fond of computer science theory. i loved studying finite-state automata

Dream job? joke answer is "crotchety hermit of a fic writer" but i don't know that i actually want to do fic writing As A Job. also kinda screwed over by my inability to imagine futures for myself. shelving books and putting up displays in a library, maybe? did that as a volunteer thing in high school and loved it so much. or that thing i did a year or two ago where i was a research assistant working under my history of cartography professor and all i did was spend four hours a day reading papers about maps and looking at digital archives. that was the most consistently happy i've been in recent memory, but that might've also been the 4-hour workday and not living with my parents

tagging, for people to engage with if desired: @coldwind-shiningstars @irrealisms @ciaran

[ani-nexus]

SITE BUZZ

[://GENRE] Cyberpunk Ghost in the Shell, Psycho-Pass, Cyberpunk 2077, Nier: Automata, Horizon Zero Dawn, Gundam: Witch of Mercury, Knights of Sidonia all had a baby. All the same terms will be used such as: hue, Sibyl System, Ghost, Cyber Brain, and so on. [://PREMISE] Thousands of years ago, a series of nuclear explosions as part of a global political act ended the world. Try as people might with better equipment and understanding of Nuclear power than ever thanks to the Chernobyl incident of 1986, the eruptions were too many and the radiation too powerful. Firefighters, liquidators, miners, "bio-robots," and more all sacrificed themselves across the world to contain the radiation. But to no avail. In what was once called the Americas, the waters had become polluted with dangerous levels and seeped over seas. That was it. Earth became uninhabitable. Hundreds of millions of lives were lost with a short period of time. Underground lead shelters that also served as research labs became the last beacons of humanity. Yet even those bases, too, eventually failed with people dying in droves due to radiation poisoning and cancer caused by radiation. The last few bases worked together to send people to outer space. DNA samples taken from ancestral hubs were brought to the stars along with the remaining few survivors. With an estimation of Earth being uninhabitable for the next 26,000 years, the last strings of humanity never expected humanity to go back. Which is what brings us here to our current period in the space colony of Rakuen. Earth was destroyed by "latent criminals gone violent." To prevent a catastrophe of this magnitude, humanity created The Sibyl System: a system that can gauge a person's stress levels and "psycho-pass" to gauge whether they're clear, cloudy and in need of therapy, latent criminals in need of incarceration before they act on criminal impulses, or a danger society to be put down. Over the years, peoples needs and wants have evolved them as well from cybernetic enhancements. These enhancements range from needed prosthetics to voluntary cyberware upgrades. There are cyberware only military can have, cyberware civillians can have, and outright blackmarket cyberware. Currently, a cyberbrain is considered illegal cyberware and has yet to be successfully crafted. In more recent times, AI and AI-made Mecha attachments have been sent to earth under the guidance of operators to assess Earth's conditions and preserve what history there is to preserve. Safe materials and specimens are to be to a shuttle called The Bunker for further examination. With resources being finite in space, this is a vital mission to keep organics alive and well. Though the aforementioned is a swan song to return Home, human or cyborg pilots of full-sized mecha are sent off on missions to explore other planets and dimensions for the same purpose: to return with safe resources and specimens, as well as to see if a planet is safe to inhabit. To help with the resource issues, humans have been genetically modified over the years to be able to synthesize in sunlight to get the nutrients they need. This need is even less so with cyborgs with abdominal replacement. [://premise_continued] There are more features to this setting such as, but not limited to: a fully ai lifestyle (their decorations and style of clothing are holographic/ai), flly immersive virtual reality for forums and games, and more. There are also unique occupations in this setting. Aside from the occupations that can be gleaned from the passages above, there is also the arena (think Arcadion for FFXIV players), spacenautical professionals (run light houses in space, catch fish in space, etc), among others. [://NO_CURRENCY_NO_LEVELLING_JUST_AWARDS] There will be no currency or levelling systems of any kind. Instead, you can aim to collect up to 80+ awards (screenshot provided below). We may get a few more awards along the way. As the site won't have staff-run events, awards are to help you to achieve certain goals and act as basic prompts when you're out of thread or plot ideas. This includes reaching certain post goals, posting up rumours or urban legends, investigating urban legends that have been posted, running events of your own based around your character's story or something else, exploring Narak (formerly known as Earth), and more. [://FULLY_AUTOMATED] - You don't need to wait on staff for almost anything. - Automatic trackers in your profiles. Just post to an IC thread once and it'll track your posts. - Move your own threads to Archives that you and other members can view (guests can't view the site). - Automatic Face Claims. - Grab your member groups yourself in Shop (mandatory) - Grab all but 3 badges yourself from the shop. (Badges you can't get yourself are: joined in first month, server booster, and generous server booster). [://PROFILES] - Don't get reviewed - Are 99% optional. Only psycho-pass + faceclaim if you have one is required - Can use animanga art as FC per normal, but can also use anime style 3D art like screenshots of your WoL from FFXIV. - FCs and characters will still need to adhere to rules and site premise. - FCs will be optional; you can use vibe pictures like scenery instead though it still needs to be in an animanga style. No photos or ai generated imagery allowed. [://MEMBER_GROUPS] Are based on psycho-pass hues: - white, yellow, green = clear (or unreadable) - green, blue, purple = cloudy - purple, red, black = criminal (latent or otherwise) - cymk = all OOC accounts [://AC] - No AC, but I'll do a quiet clean swoop once every 2-4 months depending on my schedule - You're expected to post once a week. Exception is if you post and tag your partners in hiatus. Any IC post is allowed including: oneshots, communications (e.g. IMs), regular posts, event participation, etc. - No word count, meaning there's no reason you can't post once a week (unless you have a hiatus notice). [://SEMI_PRIVATE] Regularly advertise like a normal RP, but people will need to fill out a form to join. [://DEADLINE_ETA] I'm going to aim for my break in summer 2025 somewhere between June-August (not sure when it is), but we'll see.

[felixcloud6288]

There's this one question on the exam I'm grading where a non-insignificant number of students gave me an answer that is 100% correct and wrong.

The question asks them to make a non-deterministic finite automata (NFA) that determines if a string has certain characteristics. Several people submitted a deterministic finite automata (DFA) instead.

And the thing is, it's easy to argue that a DFA is also an NFA so as long as there are no problems with it, I give them full credit. But it really goes against the spirit of the question. They're not showing they understand how a NFA works.

Also, DFAs are way harder to correctly make. I've penalized a LOT of the DFA answers because a DFA has far more opportunities to be wrong than an NFA.

[thefirstknife]

I love that you pointed out the Conway's Game of Life connection because:

In a cellular automaton, a puffer train, or simply puffer, is a finite pattern that moves itself across the "universe", leaving debris behind. Thus a pattern consisting of only a puffer will grow arbitrarily large over time. While both puffers and spaceships have periods and speeds, unlike puffers, spaceships do not leave debris behind.

In a cellular automaton, a gun is a pattern with a main part that repeats periodically, like an oscillator, and that also periodically emits spaceships.

Hmm I wonder how both the image and the descriptions seem so familiar

Yep! I really like the stuff about the game of life, I spent hours at one point just reading about it and trying it out. I think that trying it out and reading about how it works actually helps visualise the game from Unveiling a lot better. I think it also adds to the allegory once you understand what the game looks like.

The animation for this thing you screenshot btw:

Another thing I'd like to add is that this game was mentioned before the Unveiling, back in Forsaken. In Awoken of the Reef, which is basically just an extension of Marasenna, in one entry, Mara has several dreams which alert her to the threat of Oryx and the need to prepare to fight him. One of her dreams is the following:

SHAPES AND GLIDERS. I dreamt of existence as a game of cellular automata. In this metaphor, there were only two things: shapes in the game world and the rules of the game world. The rules were the rules of Life and Death. I understood that the sword was the desire to escape existence as a shape in the game and to become the rule that made the shapes. This rule said only "live" or "die"—it had no other outputs. It could not keep secrets. Against it was the desire to become a shape so complex that it could within itself play other games.

This references the same game, especially with the term "gliders" because that's one of the repeating shapes from the game of life. This is a glider:

I'm wondering about this quite a lot since the whole Witness reveal and renewed interest in the Unveiling. Mara saw this metaphor too, way before any of us read about it in Unveiling. For her, the metaphor extended to reveal Oryx's arrival. We also know that Mara has known about the Black Fleet and the Witness for longer than most as well, so I'm additionally wondering if this dream exposed her to some of the Witness' manipulations super early. It's an interesting little detail that's also relevant because the same writer wrote both this and the Unveiling.

[goqmir]

my deterministic finite automata is kind of uteruscore. terfs die go away get shot by shotgun 9 million shells

[crownine24]

Dogs were simply never meant to make non deterministic finite automata. This is beyond me

[sisyphusdust]

sketch for ease ; for future - NAND/Sheffer stroke + set notation for chronology

anyway-

Two lines of code produce the Mandelbrot set

It is a series being tested for complex numbers in a complex plane for every point and for those where the series is diverging, u paint this black and where it’s diverging u don’t and u get the intermediate colours by taking how fast it diverges

This gives the shape of the fractal

Consider inhabiting this fractal and u have no access to ur location in the fractal. Nor have u discovered the generator function yet. All you can see is that the spiral moves a little bit to the right. This is an accurate model of reality in so far that it is not wrong.

It only appears like this to an observer that is interpreting things in finite dimensions and then defines certain regularities in there - - at a certain scale that is currently observed. If you adjust ur scale ( e.g. zoom in) the spiral might disappear or appear differently at another resolution. At this level, u have the spiral and then you find the spiral moves to the right and at some point it disappears. So u have a singularity

Now - ur model is no longer valid. U cannot predict what happens beyond the singularity. But u can observe again and you will see the singularity in another spiral. And it this point it disappears. Map the points of disappearance ( “singularities”) and in the case of observing two we know of a second order law. Make e.g. thirty of these laws then u have a description of the world that is similar to the one we arrive at when describing the world around us. Reasonably predicting but doesn’t reach to the core (root[s]).

Beyond the singularity is inaccessible to mathematics/science. Consider being embedded in something analogous to the Mandelbrot set and u want to understand how it works. U arrive at this notion that it must be some kind of automation and perhaps u can just enumerate all the possible automata until u reach the one that produces ur reality.

So u need to identify necessary and sufficient conditions. For instance discovering that mathematics itself is the domain of all language

Insert:

- Huxley

- Wittgenstein

Need to find fundamental rules of cellular automata then or those of the generalisation behind everything

#joschabach

[0x4468c7a6a728]

What is the magic robot stuff you do? The one that looks like a glyph to control a construct.

i assume you're probably talking about the automata posts i did a bit ago? those posts are all state diagrams of a type of finite state machine, specifically nondeterministic finite automata. Essentially they check if a string belongs to a specific regular language, so they're kinda just a different way of expressing a regular expression? idk if that's a great explanation but i think they're fun :3

[apersonshapedcomputer]

Software Dev who graduated 2023 here with an anecdote! One time during senior year I had a computational theory class where we did homework in pairs (do the work separately, compare work, refine). The homeworks took hours and involved painstakingly drawn diagrams of finite automata and Turing machines. I made beautiful LaTeX documents of these arcane glyphs that caused me such grief.

Eventually my homework partner tried plugging one of the questions into chatgpt in what I can only guess was a bout of frustrated despair over a tricky question. It's solution to "give steps for building a Turing machine that does A, B, and C" was "first build a Turing machine that does A, B, and C". This was worse than useless and we instead went with my less dubious hand calculated solution.

I have a deep distain for "vibe coders" and various flavors of ai/tech-bros for a multitude of reasons. There's the environmental cost for one thing. Then there's the utter disregard for the amount of thought and planning that goes into writing good, easily debuggable software (there's gonna be some truly tragic legacy code spawned from all this nonsense). Of course there's the huge potential for safety issues; the ai can and will hallucinate package dependencies that break everything.

If you need a piece of software built and are hiring a programmer, make sure they know how their own code works and aren't just plugging in whatever the ai spat out. Make sure they've considered all the ways a user could break the code and found ways to protect against that. See if they have documentation for their code, and if it is 1) readable and 2) things work the way it says they do in the documentation.

This has been a rant by an angry programmer.

ur future nurse is using chapgpt to glide thru school u better take care of urself

[globalintellectualbeverage]

For all the Finite State Automata out there

[felixcloud6288]

In case anyone's interested in understanding that math thing I posted yesterday, what I posted was something called the Pumping Lemma for Regular Languages.

A lemma is a minor theorem which has no real use outside its ability to be used for other proofs.

If you have a Regular Language, the Pumping Lemma is true by definition, and it cannot be used to prove a language is Regular. BUT, if you prove the Pumping Lemma cannot apply to a Language, you can use that to prove the Language is NOT Regular.

Read more for the journey about all this

Automata

Don't worry. This is not as complex as it sounds. An automata has a number of states that it operates in and a set of rules revolving around how it transitions between states.

Consider a calculator. You press certain buttons on it and it will display an output depending on the sequence you pressed. If you press '0 1 =', the calculator prints '1'. If you press '1 7 + 4 =', the calculator prints '21'. But if you press '1 / 0 =', the calculator throws an error. And if you press '1 + =', that also throws an error.

On the underside of the calculator, there's a set of logic responsible for processing your input. It contains a finite number of states that represent what inputs the calculator has read, a set of rules about how to transition between states, and maybe some other components depending on the machine. But not every sequence of input is recognized by the calculator.

In general, the set of all input sequences a machine recognizes is called its Language. And the set of all inputs it can process is called its Alphabet.

Regular Languages

Regular Languages are a particular type of Language. They are Languages that can be recognized by a specific automata called a Deterministic Finite Automata (DFA).

DFAs have five components to them:

A FINITE number of states

The Alphabet of the automata

The transition rules of the automata

The Start State

The Final States

The transition rules work as follows: If there is a rule that says something like (A, x) -> B, that means if we are currently on State A and read input x, we now transition to state B.

The Start State is one specific state in the DFA which we always start at. The Final States are a subset of the DFA's states where if any of them are the active state after reading the final input, the DFA accepts the input as part of the language.

So the way the DFA runs is you initially start in the Start State. Then for each input, you jump to another state based on the transition rules. You keep doing this until all the inputs are read. If the last state you're in is one of the Final States, then the input is accepted as part of the Language. Otherwise, it is rejected.

Here's a DFA which recognizes any sequence of 0's and 1's where the last two characters are '01'.

Each circle is a state in the machine.

q1 has a singular unlabeled arrow pointing to q1 indicating that is the start state. q3 is the Final State, indicated by the double circle.

Each labeled arrow represents a transition rule. For example, if we are in q1 and read a '0', we go to q2.

Some sequences that will be accepted are '101', '01', and '001101'. Some inputs sequences that will not be accepted are '1', '010', and '011'.

Pumping Lemma for Regular Languages

Consider the sequence '001101' for the earlier Language. Notice how there are more characters in the sequence than there are States in the DFA. That is because the DFA has a loop in it. You can go from q1 to q2 to q3 and back to q1. You can repeat a looping sequence as many times as you want and you'll still have a sequence in the language.

Here's the more technical definition for Pumping Lemma:

If you have a regular language L, there's a certain value P, called the Pumping length. If there is a string s which is in L whose length is greater than or equal to P, then you can apply the Pumping Lemma to it.

In that case, s can be broken down into three strings xyz. x is whatever comes before the part that loops, y is the first iteration of the looping part. z is everything after the loop.

The total length of xy is less than or equal to P. Meanwhile, the length of y is greater than 0.

After defining x, y, and z; you can then insert or remove y as many times as you want from your string, and you still have something that is accepted by the DFA.

So as an example, lets go back to '001101'. Let's say P=2 (because '01' is the smallest string we can create with the above DFA). 001101 is 6 characters long so we can pump it. And we can define x='0', y='0', z='1101'. This fits the requirement of xy's length being less than or equal to P, and y's length being greater than 0.

xz = '01101' which will be accepted.

xyyz = '0001101' which will be accepted

xyyyz = '00001101' which will be accepted

Using the Pumping Lemma

The Pumping Lemma cannot prove a language is regular because it's a characteristic of a Regular Language. BUT, you can prove a language is NOT regular by showing the Pumping Lemma doesn't work.

Let's consider a Language L that accepts any sequence of 0's and 1's where the number of 0's is the same as the number of 1's. So '01', '0110', and '001101001011' are in the language.

This language is not regular. We can prove it's not regular by showing a scenario where the Pumping Lemma will never work.

If the Pumping Lemma were true, we could choose P, then choose an xyz for any pumpable string in L.

Since we're trying to disprove the Pumping Lemma, things are inverted. We instead choose a string that will always be pumpable regardless of P. And we choose how many times we pump y which will generate a string that is NOT in the language.

So now let's show that the above language is not regular. We cannot choose our pumping length. But we can choose a string in L. We'll choose s = '0^P1^P'. This string is P '0''s followed by P '1''s. So if P=1, s = '01'; if P=2, s='0011' etc.

We cannot define how we split s into x, y, and z. But we can define roughly what they could be by the definitions in the Pumping Lemma. The length of xy is less than or equal to P, so that means xy is at most the P '0''s in s. And the length of y is greater than 0. Combining both rules means y is at least one of the '0''s in the first half and y is NOT ever going to be any of the '1''s. To simplify some things, we'll say y = '0^n' where n is any number from 1 to P.

Now consider if we pump y twice to make xyyz. xyyz = '0^(P+n)1^P'. xyyz is NOT in our language because we have a string which has more 0's than 1's. But if L was regular, xyyz should be in L. Since that's not the case, this means L cannot be a regular language.

Conclusion

So hopefully, you have a rough idea of how this worked. One of the utilities of this concept is determining the minimal amount of complexity needed to perform a certain task.

Regular Languages and their accompanying DFAs are amongst the simplest Languages and automata. They have no memory, cannot recall anything they've processed previously, and have no idea about what will happen in the future.

They only know exactly where they are in the moment and what they can do immediately from there. When a DFA is in a particular state, it does not know how it got there. It knows what states it can immediately go to, but it has no idea where it can go after.

So if you're trying to build a particular automata and you think it's simple enough to build with a DFA, you need to run it by this proof. If the Pumping Lemma can break, then your automata needs a more complex structure.