Applications of Finite Automata - Theory of Computation | EduRev Notes

Theory of Computation

Computer Science Engineering (CSE) : Applications of Finite Automata - Theory of Computation | EduRev Notes

The document Applications of Finite Automata - Theory of Computation | EduRev Notes is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Part VII. Applications of Finite Automata
Finite automata has several applications in many areas such as

compiler design,
special purpose hardware design,
protocol specification etc..
Some of the applications are explained below:

1. Compiler Design
Lexical analysis or scanning is an important phase of a compiler. In lexical analysis, a program such as a C program is scanned and the different tokens(constructs such as variables, keywords, numbers) in the program are identified. A DFA is used for this operation.
For example, finite automation to recognize the tokens, ’while’ keyword and variables are shown below:


Applications of Finite Automata - Theory of Computation | EduRev Notes


The well known lexical analyser tool, Lex uses DFA to perform lexical analysis.

2. Hardware Design
In the design of computers, finite automation is used to design control unit of a computer. A typical sequence of operations of a computer consists of a repretition of instructions and every instruction involves the actions fetch, decode, fetch the operand, and execute. Every state of a finite automation represents a specific stage of instruction cycle.

3. Protocol Specification
A system is composed of an interconnected set of subsystems. A protocol is a set of rules for proper coordination of activities of a system. Such a protocol can be described using finite automations. An example of a bank is ahown below:
Applications of Finite Automata - Theory of Computation | EduRev Notes


State 1:
      State 1 represents the entry of a customer.
State 2:
      After he wishes to credit some cash to his account, system is in state 2.
State 3:
      Then the cashier receives cash. It reaches state 3.
State 4:
      Then the cashier updates the acoount and reach the final state 4.
State 5:
      If the customer wants to withdraw cash, he submits the slip ans system reaches state 5.
State 6:
      Then the slip is verified to confirm that he has sufficient balance and reaches state 6.
State 7:
      Then the customer is paid cash and reaches state 7.
State 8:
      Then the customer account is updated and system reaches final state 4 of the transaction.

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

pdf

,

Important questions

,

Summary

,

Objective type Questions

,

Previous Year Questions with Solutions

,

MCQs

,

Applications of Finite Automata - Theory of Computation | EduRev Notes

,

practice quizzes

,

video lectures

,

Semester Notes

,

Free

,

Applications of Finite Automata - Theory of Computation | EduRev Notes

,

Applications of Finite Automata - Theory of Computation | EduRev Notes

,

Exam

,

mock tests for examination

,

study material

,

Viva Questions

,

ppt

,

past year papers

,

shortcuts and tricks

,

Extra Questions

,

Sample Paper

;