Tag Info

Hot answers tagged

20

All a thread does is interleave operations so that parts of the process appear to overlap in time. A single-core machine with multiple threads merely jumps around: it executes small bits of code from one thread, then switches to another thread. A simple scheduler decides which thread is highest priority and is actually executed in the core. On a ...


19

A Safe (event triggered) States: Multiple "locked" states, one "unlocked" state Transitions: Correct combinations/keys move you from initial locked states to locked states closer to unlocked, until you finally get to unlocked. Incorrect combinations/keys land you back in the initial locked state (sometimes known as idle. Traffic Light (time triggered | ...


14

Any single-threaded program running on a machine with a finite amount of storage can be modelled as a finite state machine. A particular state in the finite state machine will represent the specific values of all relevant storage—local variables, global variables, heap storage, data currently swapped out in virtual memory, even the content of relevant ...


14

What you are experiencing is called 'Code Smell' and is a good indicator that you might be doing something wrong. Luckily though, you saw the problem and already came up with a great solution, so there's not much for me to say here. A state machine works perfectly for what you're doing here. Drawing it out might also help to try and find other states you ...


13

The use case that exceptions were designed for is "I just encountered a situation that I cannot deal with properly at this point, because I don't have enough context to handle it, but the routine that called me (or something further up the call stack) ought to know how to handle it." The secondary use case is "I just encountered a serious error, and right ...


12

There's a detailed discussion of this on Ward's Wiki. Generally, the use exceptions for control flow is an anti-pattern, with notable situation and language specific cough exceptions cough. As a quick summary for why, generally, it's an anti-pattern: Exceptions are, in essence, sophisticated GOTO statements Programming with exceptions therefore leads to ...


11

Border Gateway Protocol Example BGP is a protocol which backs the the core routing decisions on the internet. It maintains a table to determine the reachability of hosts from a given node, and made the internet truly decentralized. In the network, each BGP node is a peer, and uses a finite state machine, with one of six states Idle, Connect, Active, ...


7

No, your deterministic finite automaton is incorrect. Your regular expression is. The problem in your DFA is the declaration of 5 and 6 to be terminal nodes. A testcase such as "0." will be accepted by your DFA even though it should not. Optional values I want to point out how you can model a general structure which includes optional values. Let's take ...


6

They're useful for modelling all kinds of things. For example, an election cycle can be modelled with states along the lines of (normal government) --election called--> (early campaigning) --Parliament dissolved--> (heavy campaigning) --election--> (vote counting). Then either (vote counting) --no majority--> (coalition negotiations) --agreement reached--> ...


6

There's an error in this paper. Wagner claims this is boolean algebra, but also includes 'UNKNOWN' as a value along with TRUE and FALSE. Therefore, this is not actually boolean algebra but a trinary system of his own creation. Notably, he does not define NOT with respect to this trinary system. This is a classic gotcha in trinary systems. Unlike a ...


6

Nondeterministic automata can have far fewer states, but the engine to evaluate them must be capable of being in multiple states at once - all possible states. This can lead to a trade-off between memory requirements and code complexity when executing the automaton. Personally, though, I think the more interesting issues relate to how you manipulate the ...


6

Writing blocking functions is for people who can't create state machines ;) Threads are useful if you can't get around blocking. No fundamental computer activity is truly blocking, it's just that lots of them are implemented that way for ease of use. Instead of returning a character or "read failed", a read function blocks until the whole buffer is read. ...


6

Exceptions are as powerful as Continuations and GOTO. They are a universal control flow construct. In some languages, they are the only universal control flow construct. JavaScript, for example, has neither Continuations nor GOTO, it doesn't even have Proper Tail Calls. So, if you want to implement sophisticated control flow in JavaScript, you have to use ...


6

Based on what you've said in comments, this is how I would handle it: Implement the story as a finite state machine, with a twist. Each State is a page of the story, and each Transition is a link from one page to another. But each Transition also has Conditions. The Conditions could be null, in which case the Transition always shows up as an available ...


5

Every state machine has some sort of event handler and a means to trigger those events. That handler takes as input the existing state and type of event, chooses the new state, and optionally runs some side effect code. Essentially, while in state B, your main event handler forwards any events it doesn't recognize to B's event handler and remains in ...


5

Yes it can, but only in a practically useless sense. The computation engines we usually use today are ultimately equivalent to Turing machines, which do exactly what you describe (in fact, they do less, because they have only linear-access memory to work with rather then random-access memory, but it can be proved that this makes no difference). But the ...


4

How does one achieve multi-threading functionality in high-level language, such as Java, using only one thread and state machine? For example, what if there are 2 activities to perform (doing calculations and doing I/O) and one activity can block? What you're describing is called cooperative multitasking, where tasks are given the CPU and expected ...


4

The issue is not whether something "is" or "isn't" a finite state machine. A finite state machine is a mental model that may be useful for understanding something if that thing can be thought of as one. Typically the finite state machine model applies to things with a small number of states, such as a regular grammar, or the instruction sequencer of a ...


4

Regular expressions are implemented as finite state machines. The transition table generated by the library code will have a failure state built in, to handle what happens if input does not match the pattern. There's at least an implicit transition to the failure state from almost every other state. Programming language grammars are not FSMs, but the ...


4

The point of a finite state machine is that it has explicit rules for everything that can happen in a state. That's why it is finite. For instance: if a: print a elif b: print b Is not finite, because we could get input c. This: if a: print a elif b: print b else: print error is finite, because all possible input is accounted for. This ...


4

From Wikipedia: State commonly refers to either the present condition of a system or entity... That's pretty much what it means in a computing context: the data that defines the condition of some object or system. The meaning of 'state' isn't specific to programming. There are examples of 'state' literally everywhere you look. The television is off. ...


4

There are no silver bullets in design or architecture. ( Sorry ) It sounds like you're still at the beginnings of the Design phase and I think you need to focus more on the "divide and conquer" aspects of mapping out your application. Rushing into the lower level details before you have a comprehensive design means you may miss otherwise "obvious" ...


4

I think the answer is in the title: you need a rules engine. If you are planning to write your application with Java, you of course can write your own as Gilbert Le Blanc suggested, OR you might want to take a look at Drools, a rules engine. what options does a player have given the situation and his current state With Drools, or any other rules ...


3

http://swtch.com/~rsc/regexp/regexp1.html gives you a good overview of the differences between NFAs and DFAs, as well as concrete information for how to make DFAs do things that most people don't think that they can do (find the boundaries of subpatterns). The reason why most people don't know that is possible is because most programmers get their ...


3

The best way to avoid this is Automated Testing. The only way to have real confidence about what your code does based on certain inputs is to test them. You can click around in your application and try to do things incorrectly, but that does not scale well to ensure you don't have any regressions. Instead, you can create a test that passes bad input into a ...


3

I am sure you already know this but just in case: 1 Make sure every node in the state diagram has an outgoing arc for EVERY legal kind of input (or divide the inputs into classes, with one outbound arc for each class of input). Every example I have seen of a state machine uses only one outbound arc for ANY erroneous input. If there is no ...


3

This sounds awfully like some homework, so I'll refrain from giving a more detailed answer, but considering inputting a Turing machine: You can encode every Turing machine into a string (read up on Gödel numbers on that) The halting problem only ever becomes a problem at all, if a Turing machine is simulated/running in some way. When you input a string ...


3

It's completely possible to handle error conditions without the use of exceptions. Some languages, most notably C, don't even have exceptions, and people still manage to create quite complex applications with it. The reason exceptions are useful is they allow you to succinctly specify two essentially independent control flows in the same code: one if an ...


3

You could implement your washing machine as a state machine, but there's just as much potential for state proliferation as there is for if statements if you don't do things carefully. Working in states requires a different mindset where you think in terms of states (where you are), stimuli (what you get from the outside) and actions (what you do). In that ...


2

The CSV parser used in the jquery-csv plug-in It's a basic Chomsky Type III grammar parser. A regex tokenizer is used to evaluate the data on a char-by-char basis. When a control char is encountered, the code is passed to a switch statement for further evaluation based on the starting state. Non-control characters are grouped and copied en masse to reduce ...



Only top voted, non community-wiki answers of a minimum length are eligible