All geek questions in one place

Real-world use of DFA, NFA, PDA, and Turing

Now I am reading the course "Theory of Computing". I understand these concepts well. I can solve the problems. And when I asked my instructor about the real world application, he said that these concepts would certainly be useful and important in the design of the compiler. But, at least for meaningful study, I need some explanations of how I can use these concepts in my coding.

eg. If I want to create my own grep. I will use string functions in C. I do not know how to use regular expressions in coding there.

The same case applies to Turing machines.

If I want to add two numbers, why should I go with these unary concepts. Does equipment use these concepts?

+6
source share
2 answers

This article has a practical discussion on DFA and NFA, as they are used to efficiently match regular expressions. It discusses which real libraries use the efficient Thompson NFA method.

Turing machines are primarily practical as defining a computer. If someone tells me about a new language, I can test it as powerful (not to be confused with ease of use), as they say, C or Java, trying to build a Turing machine in it.

+9
source

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

Turing machines . I do not think this has a different application than its original academic purpose.

+4
source

Source: https://habr.com/ru/post/897553/

More articles:


All Articles