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?

  • $\begingroup$ It's a bit hard to understand what you're getting at. $\endgroup$ – Yuval Filmus Jan 10 '17 at 18:37
  • $\begingroup$ @YuvalFilmus sorry having a bad time in english class :( $\endgroup$ – brendan Jan 11 '17 at 6:40

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

  • $\begingroup$ thanks for the video. I am more into complexity now, throwing back the same question i asked for @YuvalFilmus ... "For example, we know that parity checker is an application of the finite state automata. But, how to we analyze the complexity inside it? and does the parity checker face any decidability problems?" thanks for your help $\endgroup$ – brendan Jan 11 '17 at 6:39
  • $\begingroup$ Without getting into what is "parity check" and assuming it is an application of finite state automata, it means that there exists a DFA which is "full" and recognizes "parity check". for any word w in length n, it will take you n steps to compute whether or not w belongs to parity check language or not. Each character is examined once, then if the input is in length of n the time complexity will be O(n) which is an amazing complexity to be at. $\endgroup$ – Gal Rettig Jan 11 '17 at 17:34

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.

  • $\begingroup$ For example, we know that parity checker is an application of the finite state automata. But, how to we analyze the complexity inside it? and does the parity checker face any decidability problems? $\endgroup$ – brendan Jan 11 '17 at 6:37
  • $\begingroup$ @brendan I can't understand your questions. I suggest you discuss them with the teaching assistant in your class. $\endgroup$ – Yuval Filmus Jan 11 '17 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.