Transition Diagram Computer Science Engineering (CSE) Notes | EduRev

Compiler Design

Created by: Cstoppers Instructors

Computer Science Engineering (CSE) : Transition Diagram Computer Science Engineering (CSE) Notes | EduRev

The document Transition Diagram Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Compiler Design.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

4.3 TRANSITION DIAGRAM:
Transition Diagram has a collection of nodes or circles, called states. Each state represents a condition that could occur during the process of scanning the input looking for a lexeme that matches one of several patterns .Edges are CREC, Dept. of CSE Page 19 directed from one state of the transition diagram to another. each edge is labeled by a symbol or set of symbols.If we are in one state s, and the next input symbol is a, we look for an edge out of state s labeled by a. if we find such an edge ,we advance the forward pointer and enter the state of the transition diagram to which that edge leads.
Some important conventions about transition diagrams are
1. Certain states are said to be accepting or final .These states indicates that a lexeme has been found, although the actual lexeme may not consist of all positions b/w the lexeme Begin and forward pointers we always indicate an accepting state by a double circle.
2. In addition, if it is necessary to return the forward pointer one position, then we shall additionally place a * near that accepting state.
3. One state is designed the state ,or initial state ., it is indicated by an edge labeled “start” entering from nowhere .the transition diagram always begins in the state before any input symbols have been used.
 

 

                             Transition Diagram Computer Science Engineering (CSE) Notes | EduRev
 

As an intermediate step in the construction of a LA, we first produce a stylized flowchart, called a transition diagram. Position in a transition diagram, are drawn as circles and are called as states
 

 

                                                                 Transition Diagram Computer Science Engineering (CSE) Notes | EduRev
 

The above TD for an identifier, defined to be a letter followed by any no of letters or digits.A sequence of transition diagram can be converted into program to look for the tokens specified by the diagrams. Each state gets a segment of code.

4.4 Automata: Automation is defined as a system where information is transmitted and used for performing some functions without direct participation of man.
1. An automation in which the output depends only on the input is called automation without memory.
2. An automation in which the output depends on the input and state also is called as automation with memory. 
3. An automation in which the output depends only on the state of the machine is called a Moore machine. 
4. An automation in which the output depends on the state and input at any instant of time is called a mealy machine. 

4.4.1 DESCRIPTION OF AUTOMATA 1. An automata has a mechanism to read input from input tape,
2. Any language is recognized by some automation, Hence these automation are basically language ‘acceptors’ or ‘language recognizers’.

Types of Finite Automata 

  • Deterministic Automata
  • Non-Deterministic Automata.


Deterministic Automata:
A deterministic finite automata has at most one transition from each state on any input. A DFA is a special case of a NFA in which:-
1. it has no transitions on input € ,
2. Each input symbol has at most one transition from any state.
DFA formally defined by 5 tuple notation M = (Q, ∑, δ, qo, F), where Q is a finite ‘set of states’, which is non empty.
∑ is ‘input alphabets’, indicates input set. qo is an ‘initial state’ and
qo is in Q ie, qo, ∑, Q F is a set of ‘Final states’,
δ is a ‘transmission function’ or mapping function, using this function the next state can be determined.

The regular expression is converted into minimized DFA by the following procedure:

Regular expression → NFA → DFA → Minimized DF

The Finite Automata is called DFA if there is only one path for a specific input from current state to next state.
                              Transition Diagram Computer Science Engineering (CSE) Notes | EduRev
From state S0 for input ‘a’ there is only one path going to S2. similarly from so there is only one path for input going to S1.

 

Nondeterministic Automata:
                                      A NFA ia A mathematical model consists of   

  •  A set of states S.
  •  A set of input symbols ∑.
  •  A transition is a move from one state to another.
  •  A state so that is distinguished as the start (or initial) state
  •  A set of states F distinguished as accepting (or final) state.
  • A number of transition to a single symbol.

    A NFA can be diagrammatically represented by a labeled directed graph, called a transition graph, in which the nodes are the states and the labeled edges represent the transition function.

    This graph looks like a transition diagram, but the same character can label two or more transitions out of one state and edges can be labeled by the special symbol € as well as input symbols.

    The transition graph for an NFA that recognizes the language (a|b)*abb is shown

                                    Transition Diagram Computer Science Engineering (CSE) Notes | EduRev
     

5. Bootstrapping: When a computer is first turned on or restarted, a special type of absolute loader, called as bootstrap loader is executed. This bootstrap loads the first program to be run by the computer usually an operating system. The bootstrap itself begins at address O in the memory of the machine. It loads the operating system (or some other program) starting at address 80. After all of the object code from device has been loaded, the bootstrap program jumps to address 80, which begins the execution of the program that was loaded.
 

Such loaders can be used to run stand-alone programs independent of the operating system or the system loader. They can also be used to load the operating system or the loader itself into memory.

Loaders are of two types:

  •  Linking loader.
  •  Linkage editor. Linkage loaders, perform all linking and relocation at load time. "
    Linkage editors, perform linking prior to load time and dynamic linking, in which the linking function is performed at execution time.

    A linkage editor performs linking and some relocation; however, the linkaged program is written to a file or library instead of being immediately loaded into memory. This approach reduces the overhead when the program is executed. All that is required at load time is a very simple form of relocation.
     

                                       Transition Diagram Computer Science Engineering (CSE) Notes | EduRev
6. Pass And Phases Of Translation: 
Phases:
(Phases are collected into a front end and back end)
Frontend: The front end consists of those phases, or parts of phase, that depends primarily on the source language and is largely independent of the target machine. These normally include lexical and syntactic analysis, the creation of the symbol table, semantic analysis, and the generation of intermediate code. A certain amount of code optimization can be done by front end as well. the front end also includes the error handling tha goes along with each of these phases.
Back end: The back end includes those portions of the compiler that depend on the target machine and generally, these portions do not depend on the source language .

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!
24 videos|35 docs|29 tests

Up next >

Dynamic Test

Content Category

Related Searches

Important questions

,

Previous Year Questions with Solutions

,

MCQs

,

Extra Questions

,

Objective type Questions

,

practice quizzes

,

Viva Questions

,

shortcuts and tricks

,

Sample Paper

,

study material

,

pdf

,

Transition Diagram Computer Science Engineering (CSE) Notes | EduRev

,

video lectures

,

mock tests for examination

,

Transition Diagram Computer Science Engineering (CSE) Notes | EduRev

,

Semester Notes

,

Transition Diagram Computer Science Engineering (CSE) Notes | EduRev

,

Summary

,

past year papers

,

ppt

,

Free

,

Exam

;