Menu
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?
978
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.
It has a finite number of states hence called Determined Finite Automata or DFA. DFA consists of 5 tuples {Q, ∑, q, F, δ}. Q set of all states. ∑ set of input symbols. ( Symbols which machine takes as input ) q Initial state.
The Turing Machine i.e. TM is more powerful than any other machine. (i) Finite Automata (FA) equivalence: (ii) Pushdown Automata (PDA) equivalence: The Applications of these Automata are given as follows: 1. Finite Automata (FA) – For the designing of lexical analysis of a compiler. For recognizing the pattern using regular expressions.
Difference between Finite Automata and Turing Machine. 1. Finite Automata : The finite automata or finite state machine is an abstract machine which have five elements or tuple. It has a set of states and rules for moving from one state to another but it depends upon the applied input symbol.
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.
150
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.
4
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
