Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start 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.


Copy of An Application Of Theory Of CS

No description

Muhammad Raza

on 18 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Copy of An Application Of Theory Of CS

What Is Automata Theory?
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.
Vending Machines
Traffic Lights
Video Games
Text Parsing
Regular Expression Matching
CPU Controllers
Video Games
Protocol Analysis
Natural Language Processing
Speech Recognition
Another Example
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.
Full transcript