Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
You can change this under Settings & Account at any time.
Copy of An Application Of Theory Of CS
Transcript of Copy of An Application Of Theory Of CS
Deterministic Finite Automata(DFA)
A Deterministic finite automata (DFA) is represented by five-tuple i.e. M = (Q, Σ, , q0, F)
is the set of states (finite)
is the alphabet (finite)
: Q Σ → Q is the transition function
q0 is the start state
is the set of accept states
= the language of machine M
= set of all strings machine M accepts
Uses Of DFA
Video Games: Pac-Man’s Ghosts
Here we consider the classic game, Pac-Man. Lets talk
about the behaviour of ghost character. The ghosts in
Pac-Man have four behaviours:
Randomly wander the maze
Chase Pac-Man, when he is within line of sight
Flee Pac-Man, after Pac-Man has consumed a power pellet
Return to the central base to regenerate.
These four behaviours correspond directly to a four-state DFA. Transitions are dictated by the situation in the game. For instance, a ghost DFA in state 2 (Chase Pac-Man) will transition to state 3 (Flee) when Pac-Man consumes a power pellet. Here it’s DFA design.
DFA In Computer Games
For AI programming, you have the choice of deterministic or non-deterministic. Most video games have deterministic; meaning you know how the enemies will react based on different inputs. If they don’t see you, they’ll patrol. If they see you, they’ll attack you. If you hide and wait, they’ll eventually go back to patrolling. You can simulate fuzzy logic by using random numbers to change state to something random.
An Application Of Theory Of CS
Deterministic Finite Automata
Automata Theory is the study
of abstract machines and problems
they are able to solve.
a finite state machine, which belongs to one well-known variety of automaton. This automaton consists of states , transitions As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function.
Regular Expression Matching
Natural Language Processing
Let discuss about a character handling
of game in which character have some qualities i.e. he can jump, dive , duck and stand. Now make the model of it which user can perform these actions
Why are we applying DFA in games?
DFA is used to control the AI of the game. The Al model games are based on mental sequence. It can change decision by time by time. To over come this type of problem we apply the DFA to solve these types of riddles.
It make program easier and shorter as compare to implements the checkpoints or if’s statements.
DFA is generally best for AI commands. It makes easier to machine to make its move. The uses of DFA in modern age are increasing. On worldwide survey, the medical science is also work on DFA models like the searching of DNA, analyze the process of protein production and much more.