Real world uses of DFA,NFA,PDA and Turing machines

Question

I am now taking a course on Theory of Computation. I can understand the concepts well. I can able to solve the problems. And, when I asked my instructor about the real world application, he told me these concepts will be surely useful and essential in compiler design. But, at least to make a meaningful study, I need some explanations on how can I use those concepts it in my coding.

e.g. If I want to design my own grep. I will use string functions in C. I don't know how to use regular expressions there in coding.

Same case applies to Turing machines.

If I want to add two numbers why I have to go by those unary concepts. Does the hardware implement those concepts?

Interrupt

Answer 1

This article has a practical discussion of DFA and NFA as they apply to efficient regular expression matching. It discusses which real libraries use the efficient Thompson NFA method.

Turing machines are primarily practical as a definition of a computer. If someone tells me about a new language, I can check whether it's as powerful (not to be confused with ease of use) as say, C or Java by attempting to construct a Turing machine in it.

Bagasse

"attempting to construct a Turing machine in it". can you explain it. (Is it similar to attempting to write a coding for getting all primes btw 100000.i.e method of checking powerfulness by writing an sample code.) So for this purpose alone turing machines are used? Thanks for the link.It is more useful. – Interrupt

Getting those primes is just an isolated test. If I can make a Turing machine (Wikipedia has a good overview), I can find those primes, as well as solve any other computable problem. – Bagasse

^ Assuming the Church-Turing thesis. ;D – Expert

@Patrick87, don't worry. If we find something Turing machines can't compute, we'll just say it's not "effectively calculable." ;) – Bagasse

Answer 2

NFA and DFA: These two are used in compilers to create tokens from characters in the source file and return them to the grammar parser. You can learn more from the UNIX lex and yacc manual.

Turing Machines: I don't think this has a different use than its original academic purpose.

Fredelia

about "Turing Machines": then why turing machines were used? why it is invented? or why those concepts came? – Interrupt

In order to be able to define what was computable or not, Alan Turing first had to create an abstract machine capable of calculate everything computable. This is where Turing Machines started. If this abstract machine could not solve the problem, then it was unsolvable. You can find more information in the original paper "On Computable Numbers, with an Application to the Entscheidungsproblem". Note that this is not the only work along these lines. There is also work from Alonzo Church and his Lambda Calculus. This also solve the computability problem. – Fredelia

To add to the comment by luis: Turing machines were introduced to systematically study the nature of computation itself, thereby defining the notion of computability – Boudoir