FORMAL TRANSITION MODELS…
FORMAL TRANSITION MODELS
Formal Transition Model என்பது ஒரு program execute ஆகும் போது, அதன் state ஒரு நிலைமையிலிருந்து மற்றொரு நிலைக்கு எப்படி மாறுகிறது என்பதை mathematical / formal rules மூலம் represent செய்யும் model. Simple Tamil: Program execute ஆகும்போது Cur…
Premium — locked
Advanced
30 min
291 cards
52 programs 10 MCQs v2
This is a premium lesson. You can see the shape of every card — unlock to read them.
Unlock
Definition
Formal Transition Model என்பது ஒரு program execute ஆகும் போது, அதன் state ஒரு நிலைமையிலிருந்து மற்றொரு நிலைக்……
Definition
1. TRANSITION என்றால் என்ன?…
Definition
Transition = ஒரு state-இலிருந……
Program
Example
Program
Initially
Program
After executing
Program
New state
Explanation
Therefore: x = 5 ↓ x = x + 1 ……
List
1. STATE என்றால் என்ன?…
Definition
ஒரு குறிப்பிட்ட நேரத்தில் program-ன் variables, memory மற்றும் execution infor……
Explanation
Example
int x = 10; int y = 20; Curre……
Explanation
இதனை mathematical form-ல்: σ = {x → 1……
STATE MAPPING
Explanation
State பொதுவாக: Variable → Value mapping ஆக பார்க்……
FORMAL TRANSITION
Explanation
State transition-ஐ formal-ஆக: σ → σ' என்று represent……
Explanation
After: σ' = {x → 6} Thus: σ →……
CONFIGURATION
Explanation
Formal semantics-ல் state மட்டும் இல்லாமல், தற்போது execute செய்ய வேண்டிய statement-ஐயும……
TRANSITION NOTATION
Explanation
A common notation: → Where:…
Explanation
C' = Remaining command σ' = New state Simple: Pro……
SIMPLE ASSIGNMENT TRANSITION
Program
Consider
Explanation
Before: σ = {x → 5} After: σ' = {x → 1……
EXPRESSION TRANSITION
Program
Example
Explanation
Step 1: 2 + 3 evaluate: 5 Ste……
Explanation
Then state update: x → 5 Flow……
TRANSITION SYSTEM
Definition
States மற்றும் அவற்றுக்கிடையிலான tra……
Explanation
General form
State ↓ Transition ↓ State A transition system……
FORMAL TRANSITION MODEL - COMPONENTS
List
Main components
1. State 2. Initial State 3. Transition ……
Explanation
Program execution ஆரம்பிக்கும……
FINAL STATE
Explanation
Program execution முடிவடைந்த ……
Program
Example
Program
Final
STATE TRANSITION SEQUENCE
Program
Example
Program
State 0
Program
State 1
Program
State 2
Program
Therefore
Explanation
S₂ {x=9}…
List
1. WHY FORMAL TRANSITION MODE……
Explanation
Programming language semantics natural language மட்டும் use செய்து describe செய்தால் ambiguity வரலாம். Formal……
OPERATIONAL SEMANTICS
Explanation
Formal transition models-க்கு ம……
Definition
Program statements execute ஆகும்போது machine state எப்படி change ஆகிறது என்பதை formal transition r……
OPERATIONAL SEMANTICS IDEA
Explanation
Program
+ State ↓ Execution Rule ↓ Ne……
Program
Example
Program
State
Output
Result
TWO IMPORTANT OPERATIONAL MODELS
Small-Step Semantics
Big-Step Semantics
இதனை மிகவும் முக்கியமாக படிக்……
SMALL-STEP SEMANTICS
Definition
Program execution-ஐ one small computation step at a tim……
Program
Example
Explanation
Small steps: 2 + 3 ↓ 5 Then:…
SMALL-STEP NOTATION
Explanation
Common notation: → One arrow:……
MULTIPLE SMALL STEPS
Explanation
Multiple transitions: →* can ……
Definition
Meaning
Command C பல small steps exec……
BIG-STEP SEMANTICS
Definition
Program-ன் intermediate execution steps காட்டாமல், initial stat……
BIG-STEP EXAMPLE
Program
Initial
Explanation
Big-step: ⇓ {x=5} Symbol: ⇓ m……
SMALL-STEP vs BIG-STEP
SIMPLE COMPARISON
ASSIGNMENT RULE
Explanation
Formal assignment semantics c……
Explanation
updates state: σ[x ↦ v] Rule: < x := e, σ > → < skip, σ[x ↦ valu……
SEQUENCE
Program
Consider
Explanation
Execution: x = 1 ↓ y = 2 ↓ Final State ……
SEQUENCE TRANSITION RULE
Explanation
If: → then: →…
Definition
Meaning
First statement-ல் ஒரு step execute செய……
SEQUENCE COMPLETION RULE
Definition
When first statement complete……
Definition
Meaning
First command done; now secon……
IF STATEMENT TRANSITION
Program
Example
Explanation
Two possibilities. If: x > 0 = true……
IF TRUE RULE
Explanation
Conceptually: if b then C1 el……
IF FALSE RULE
Explanation
If b = false: →…
IF EXAMPLE
Program
Initial
Explanation
Check: 5 > 0 → true Therefore:…
Explanation
Final: {x=5, y=1}…
WHILE LOOP TRANSITION
Program
While loop
Explanation
Formal idea: while b do C can be understood as:……
WHILE LOOP EXAMPLE
Explanation
int x = 1;…
Explanation
State transitions: S₀: x = 1 ↓ S₁: x……
WHILE AS STATE TRANSITIONS
Explanation
This is a classic example of ……
TRANSITION RELATION
Definition
எந்த state-இலிருந்து எந்த state-க்கு move செய்ய முடியும் என்பதை……
Explanation
Example
S1 → S2…
Definition
Meaning
S1 state can make one valid t……
LABELED TRANSITION SYSTEM
Definition
Transitions actions/events-ன் na……
Explanation
Example
S0 --login--> S1 S1 --logout-……
LTS FORMAL STRUCTURE
Explanation
A labeled transition system can……
Explanation
Often initial state-ஐ சேர்த்த……
SIMPLE LTS EXAMPLE
Explanation
Traffic signal: Red ↓ timer Green ↓ timer Yellow ↓ timer Red Formally: Red --timer-->……
DETERMINISTIC TRANSITION
Explanation
ஒரு given state + input/action-க்கு onl……
Program
Example
Program
Next
Explanation
Only one result.…
NON-DETERMINISTIC TRANSITION
Explanation
Same state-இலிருந்து multiple possible next states இருக்க முடிந்தால்: Non-Deterministic Tran……
DETERMINISTIC vs NON-DETERMINISTIC
TERMINAL STATE
Explanation
Further transition possible இல்லாத state: Termin……
STUCK STATE
Explanation
Program normal final state-க்கு வராமல், valid transition rule apply செய்ய முடியாத state: Stuck ……
SKIP COMMAND
Explanation
Formal semantics-ல்: skip means: Do not……
BOOLEAN EXPRESSION TRANSITION
Explanation
Example
x > 5 If:…
Explanation
then: x > 5 ↓ true Boolean re……
ARITHMETIC EXPRESSION SEMANTICS
Explanation
Example
2 + 3 * 4 By precedence: 3 * 4 ↓ 1……
EXPRESSION EVALUATION AS TRANSITION
Explanation
Small-step: e → e' means: Expression e ……
FORMAL RULE FORMAT
Explanation
Formal transition rules freque……
Summary
Conclusion
Example conceptual: e → e'…
Definition
Meaning
Expression e one step e' ஆக முடிந்தால்,……
INFERENCE RULE
Definition
Known conditions/premises-இலிருந்து valid transitio……
AXIOM
Summary
Premise இல்லாமல் directly valid r……
→ No additional premise neede……
TRANSITIVE CLOSURE
If: S0 → S1 S1 → S2 S2 → S3 then: S0 →* S3 ……
ONE-STEP vs MULTI-STEP
→ = one transition. →* = zero or more ……
FORMAL MODEL OF A SIMPLE PROGRAM
Explanation
Initial: σ₀ = {x → 0} Step 1:……
PROGRAM STATE AND MEMORY
Explanation
State may contain more than variables. Advanced model-ல்: State = Environment + Store + Control……
ENVIRONMENT
Definition
Identifier-ஐ storage location / ent……
Explanation
Example
ρ(x) = L1 Means: variable x l……
STORE
Definition
Memory location-ஐ current val……
Explanation
Example
σ(L1) = 10 Thus: x → L1 → 10…
List
1. WHY ENVIRONMENT + STORE?…
Explanation
Consider: int x = 10; Two different concepts: x → Memory Locati……
CONTROL COMPONENT
Explanation
Program-ல் currently எந்த statement execute ஆகிறது என்பதைக……
TRANSITION MACHINE
Explanation
ஒரு abstract machine-ல்: Configuration ↓ Transition Rule ↓ Ne……
CONNECTION WITH VIRTUAL COMPUTER
Explanation
Earlier பார்த்த Virtual Computer concept நினைவில் கொள்ளுங்கள். Virtual Computer ↓ Has machine state ↓ Execute……
CONNECTION WITH BINDING
Explanation
Example
int x = 10; Binding: x → int ……
Explanation
binding usually same: x → sam……
Important
Binding change மற்றும் state ……
CONNECTION WITH SEMANTICS
Important
Syntax tells: How program is written. Semantics tells: What program means. Formal transition ……
FORMAL SEMANTICS TYPES
Important
Programming languages-ல் thre……
Important
1. Operational Semantics 2. D……
Important
Formal transition models mainly……
OPERATIONAL SEMANTICS
Definition
Meaning
Program meaning = How an abstract……
DENOTATIONAL SEMANTICS
Definition
Program constructs-ஐ mathemat……
Concept
Program ↓ Mathematical Meaning…
Explanation
Example
[[ expression ]] notation use……
AXIOMATIC SEMANTICS
Explanation
Program correctness-ஐ logical assertions ம……
Program
Example
OPERATIONAL vs DENOTATIONAL vs AXIOMATIC
Explanation
For your current topic: Formal Transition ……
TRANSITION MODEL FOR IF
Program
Initial
Explanation
Step: x > 0 ↓ true Then:…
Program
Transition
TRANSITION MODEL FOR LOOP
Program
Initial
Explanation
States: S0: x=3 ↓ S1: x=2 ↓ S2: ……
LOOP TERMINATION
Explanation
Formal model மூலம் loop termi……
Program
Example
Explanation
Every transition: x → x-1 Eve……
Explanation
Therefore termination expecte……
INFINITE TRANSITION
Explanation
Program never reaches final s……
Explanation
Formal transition: S0 → S1 → S2 → S3 → ... No ……
CONCURRENCY AND TRANSITIONS
Explanation
Two processes: P1 P2 can execute in different orders. State: S0 Possible: S0 --……
REACHABLE STATE
Explanation
Initial state-இலிருந்து valid transitions மூலம் reac……
UNREACHABLE STATE
Explanation
No valid transition sequence leads to a state: Unreachable……
SAFETY PROPERTY
Explanation
Formal transition model பயன்படுத்தி: "Bad state never occurs" என்று prove செய்ய முயற……
LIVENESS PROPERTY
Explanation
System eventually something good செய்கிறதா என்பதை check செய்யும் property……
FORMAL TRANSITION MODEL ADVANTAGES
Explanation
Precise semantics No ambiguity Program verification Compiler verificati……
LIMITATIONS
Explanation
Large programs-க்கு: Huge number of states Complex rules State exp……
STATE EXPLOSION
Explanation
Suppose each component has many states. Multiple components combine செய்தால் total states rapidly increas……
Flow
Formal Transition Model complete flow: Program ↓ Initial C……
Comparison
State vs Transition
Comparison
Small-Step vs Big-Step
Remember
State = Current values / memory information Transition = Change from one ……
Common Mistake
Common error
Do not confuse: State ≠ Variable Transition ≠ Assignment only Binding ≠ State Transition Syntax ……
Memory Trick
S → State T → Transition R → Rule C → Configuration F ……
TRB Point
1. A formal description of pr……
TRB Point
Answer: Formal Transition Mod……
TRB Point
1. The current values of prog……
TRB Point
Answer: State…
TRB Point
1. A change from one state to……
TRB Point
Answer: Transition…
Small-step semantics is also called:
TRB Point
Answer: Structural Operationa……
Big-step semantics is also called:
TRB Point
Answer: Natural Semantics…
Symbol usually representing one-step transition:
TRB Point
Answer: →…
→* generally represents:
TRB Point
Answer: Zero or more transiti……
TRB Point
1. A state with no further no……
TRB Point
Answer: Final / Terminal State…
Multiple possible next states indicate:
TRB Point
Answer: Non-determinism…
Formal transition models are strongly related to:
TRB Point
Answer: Operational Semantics…
MCQ
A program state represents:…
MCQ
A transition represents:…
MCQ
Which notation normally repre……
MCQ
Small-step semantics describe……
MCQ
Big-step semantics relates:…
MCQ
Which is another name for sma……
MCQ
Big-step semantics is also ca……
MCQ
If one state has two possible……
MCQ
Which formal semantics direct……
MCQ
A configuration usually conta……
TRB Point
Exam point
2 Marks - Define Formal Transition Model Formal Transition Model is a mathematical model that describes progr……
TRB Point
1. Definition 2. State 3. Configuration 4. Transition relation 5. Initial and fin……
Summary
Program ↓ Initial State S₀ ↓ Transiti……
Formula
Formal notation
→ where: C = Current command σ = Current state C' = Remaining/new command σ' = New state Most important relat……
Text size
Theme
Contents
Print / PDF