Real time application with DFA or NFA application

Question

Can anyone here give an example of DFA or NFA real time application?

And, can I know what are complexity and decidability problems in real time application? Does every real time application have complexity and decidability problems?

Answer 1

DFA/NFA in a real time application ? consider designing a parser for user inputs where each input is a word w="http://some-address.com?key[1]=value1&key[2]=value2..."

consider having each key[i] as the string ##i now you can easily build a regex /##./ to accept all input-strings having key values contained in w.

Since we have a regular expression that recognize this pattern there exists an equivalent NFA that recognizes such words, now your parser server can recognize http requests that holds information valuable to your application and distinguish them from normal static requests for pages/images.

There is a big difference from Complexity to Decidability problems, Decidability problems is a question whether for all inputs w the algorithm A will halt and yield a result, Not every problem is Decidable (i.e loop to infinity doesn't halts), moreover not every problem that is decidable has the same complexity.

problems can be solved by different algorithms Complexity analysis is about trying to understand the time/space complexity of a problem and its boundaries.

Moreover by Complexity analysis we can try and break up different problems into different classes, for example class A could be "All problems that have an algorithm solving them in (some_constant)(nlog(n) time" could be an hypothetical class of problems.

Here is some nice short video trying to summarize some of the ideas of Complexity. https://www.youtube.com/watch?v=YX40hbAHx3s

Answer 2

A real time application is one in which some computation needs to be done very fast, always. For example, controlling an airplane, decoding an MPEG, and Skype are real time applications. Web browsing is not an example since it needn't be very fast, and it is also tolerable if it is occasionally a bit slow.

You are asking for complexity and decidability problems in real time applications. This question is a bit hard to interpret. You might as well ask for complexity and decidability problems in airborne computers. What you could be asking is what kinds of problems come up when designing real time applications. Sometimes we are faced with decision problems, sometimes with function problems (requiring us to compute some function whose output is not necessarily Boolean), sometimes with interactive tasks which are not considered in classical theoretical computer science.

You then ask whether all real time applications have complexity and decidability problems. This is again hard to interpret, and this time I won't offer any interpretations.

Finally, you ask whether finite state automata have real time applications. It so happens that finite state automata and, more generally, finite state transducers are very efficient to implement, even compared to other linear time parsing algorithms such as LR parsing. Therefore they may very well be used in high traffic TCP/IP stacks, as you mention in a comment on a deleted answer.

In the same comment you ask for the meaning of real time in these examples. The meaning is that the worst case running time of simulating a finite state automaton is very small. Contrast that with garbage collection, which has a small amortized running time, but a large worst case running time. Garbage collection epitomizes what you want to avoid in real time applications.