What is the use of finite automata? [closed]_问答_开发者

Closed. This question needs to be more focused. It is not currently accepting answers.

Want to improve this question?开发者_StackOverflow Update the question so it focuses on one problem only by editing this post.

Closed 4 years ago.

Improve this question

What is the use of finite automata? And all the concepts that we study in the theory of computation. I've never seen their uses yet.

They are the theoretical underpinnings of concepts widely used in computer science and programming, and understanding them helps you better understand how to use them (and what their limits are). The three basic ones you should encounter are, in increasing order of power:

Finite automata, which are equivalent to regular expressions. Regular expressions are widely used in programming for matching strings and extracting text. They are a simple method of describing a set of valid strings using basic characters, grouping, and repitition. They can do a lot, but they can't match balanced sets of parentheses.
Push-down automata, equivalent to context-free grammars. Text/input parsers and compilers use these when regular expressions aren't powerful enough (and one of the things you learn in studying finite automata is what regular expressions can't do, which is crucial to knowing when to write a regular expression and when to use something more complicated). Context-free grammars can describe "languages" (sets of valid strings) where the validity at a certain point in parsing the string does not depend on what else has been seen.
Turing machines, equivalent to general computation (anything you can do with a computer). Some of the things you learn when you cover these enable you to understand the limits of computing itself. A good theory course will teach you about the Halting Problem, which enables you to identify problems for which it is impossible to write a program. Once you've identified such a problem, then you know to stop trying (or refine it to something that is possible).

Understanding the theory and limitations of these various computing mechanisms enable you to better understand problems and programs and think more deeply about programming.

There was a request-for-work published about a year ago on one of the freelance coding exchange sites asking, essentially, for a program which solved the Halting Problem. Several people responded with offers, saying they "understood the requirements" and could "start immediately". It was impossible to write a program which met the requirements. Understanding computing theory enables you to not be that bidder who demonstrates, in public, that he really doesn't understand computing (and doesn't bother to thoroughly investigate a problem before declaring understanding and making an offer).

Finite automata are very useful for communication protocols and for matching strings against regular expressions.

Automatons are used in hardware and software applications. Please read the implementation section here http://en.wikipedia.org/wiki/Finite-state_machine#Implementation

There is also a notion of Automata-based programming. Please check this http://en.wikipedia.org/wiki/Automata-based_programming

cheers

Every GUI, every workflow can be treated as a finite automata. Think of each page as a state and transitions occurring due to certain events. Perhaps you can't proceed to a certain page or the next stage of the workflow until a series of conditions are met.

Finite automata are e.g. used to parse formal languages. This means that finite automata are very usefull in the creation of compiler and interpreter techniques.

Historicaly, the finite state machine showed that a lot of problems can be solved by a very simple automate.

Try taking a compilers course. You will very likely make a compiler or interpreter using a finite state automaton to implement a recursive descent parser.

For example to manage states of some objects with defined life cycle. As example of this: orders in book shop. An order can have the following states: -ordered -payed -shipping -done

and program of the finite automata knows how one state can be changed by other.

The finite automata is a type of state machine (SM). In general SMs are used for parsing formal languages.

You can use as a formal language many entities, not only characters.

And regular language is a type of formal language. There are some theory that show, what type of the SM is better to parse a regular language: http://en.wikipedia.org/wiki/Regular_language