Introductie Labeled Transitiesystemen
https://www.youtube.com/watch?v=m2S495baBe0&list=PLbn9FICCNIGiORzXI6ZsnS7dZdS
KlOk1l&index=1
Wat is het gedrag van een lamp?
Een lamp kan drie dingen doen:
1. Aan gaan
2. Uit gaan
3. Kapot gaan
Een lamp kan drie dingen zijn:
1. Aan
2. Uit
3. Kapot
Wat iets of iemand kan doen noemen we acties.
Wat iets of iemand kan zijn noemen we toestanden.
Gedrag is de verzameling van toegestane acties.
Een actie is een verandering van de ene toestand naar de andere toestand
Acties kunnen we weergeven met behulp van een graaf. Hierbij worden toestanden
weergeven als een cirkel met in het midden de bijbehorende hoofdletter en worden acties
weergeven als een pijl met in het midden boven de bijbehorende kleine letter.
Zo’n graaf noemen we een Labeled Transition System (LST).
Stel je voor dat we van het gedrag van een lamp een graaf willen maken. Om te beginnen
bepaal je wat de begintoestand (initial state) moet zijn van de lamp. In dit geval bepaal ik dat
de begintoestand Aan is. Om dit aan te geven in de graaf tekenen we een pijl (zonder
begincirkel en zonder letter) die naar deze begintoestand (A) wijst.
,Daarna tekenen we de volgende actie. De volgende actie vind ik het uit gaan. Je tekent dan
een pijl van de Aan-toestand naar een nieuwe cirkel die de Uit-toestand (B) voorstelt. Deze
pijl geef ik als letter een u.
Een andere actie is Aan gaan. Dit kunnen we ook tekenen in de graaf. We tekenen dan een
pijl van de Uit-toestand naar de Aan-toestand. Deze pijl geef ik als letter een a.
,Er blijven nog een actie (kapot gaan) en een toestand (kapot) over. Deze tekenen we ook in
de graaf. We tekenen een cirkel die de toestand kapot (Z) weergeeft. Omdat een lamp zowel
wanneer hij aan als uit is kapot kan gaan, tekenen we twee pijlen: een pijl van de Aan
toestand naar de kapot toestand en een pijl van de uit toestand naar de kapot toestand.
De actie ‘kapot gaan’ is een speciale actie. Deze actie is een actie die zomaar kan
gebeuren. We noemen zo’n actie een stille actie. Bij pijlen van een stille actie schrijven we
geen letter bij. De andere acties waarbij die bewust worden gedaan noemen we zichtbare
acties.
, De graaf is bijna klaar. Het enige wat we nog moeten doen is het weergeven wat de laatste
toestand is. Deze toestand mag je zelf bepalen. Dit doen we door nog een cirkel te zetten
om de gekozen eindtoestand (final state) te zetten. Je kunt ook meerdere eindtoestanden
hebben.
Een LTS met een eindig aantal toestanden en acties wordt eindige toestand LTS (finite-state
labelled transition system) genoemd. Een finite-state labelled transition system met een
begintoestand en toegestane toestanden wordt een eindige toestandsautomaat genoemd
(finite state automaton).
Niet alleen kunnen we het gedrag met behulp van graven weergeven, maar ook met
wiskundige notaties. Je formaliseert dan een labeled transitie systeem. Je schrijft dan:
L = (S, A, →, so (of si), Ω).
- S staat voor alle toestanden. Dit schrijf je zo: S = {A, B, C, D, etc.}.
- A staat voor alle zichtbare acties. Dit schrijf je zo: A = {a, b, c, d, etc}. Deze bevat
alleen unieke letters (en niet dat als je een actie meerdere keren ziet dat je die
meerdere keren opschrijft).
- → staat voor alle mogelijke overgangen. Deze schrijf je zo: → = {(A, a, B), (B, b, C),
(C, τ, D), etc.}. Deze bevat wel de overgangen met de stille acties. Door te kijken
hoeveel verschillende soorten silent acties in de overgangen zijn, kun je weten
hoeveel silent acties er zijn.
- so staat voor de begintoestand. Er is altijd maar één begintoestand. Deze schrijven
we zo: so (of si) = A.
- Ω staat voor de eindtoestand(en). Omdat er meerder eindtoestanden zijn, schrijven
we de eindtoestand(en) in accolades. Dit schrijf je zo: Ω = {Z}
- Een stille actie wordt aangeduid met τ. De stille actie wordt ook wel een τ-stap
genoemd.
Het aantal zichtbare acties kun je vinden door het aantal letters die A bevat op te tellen. Het
aantal toestanden vind je door alle knooppunten op te tellen.
Een geformaliseerde LTS bestaat dus uit:
- S: een set van toestanden
- A: een set van zichtbare acties
- →: een overgang tussen toestanden, die bepaalt hoe het systeem van de ene
toestand naar de andere overgaat. → bevat elementen van de vorm (S, a, Z), waarbij
S de huidige toestand is, a de uitgevoerde actie is en Z de resulterende toestand is.
https://www.youtube.com/watch?v=m2S495baBe0&list=PLbn9FICCNIGiORzXI6ZsnS7dZdS
KlOk1l&index=1
Wat is het gedrag van een lamp?
Een lamp kan drie dingen doen:
1. Aan gaan
2. Uit gaan
3. Kapot gaan
Een lamp kan drie dingen zijn:
1. Aan
2. Uit
3. Kapot
Wat iets of iemand kan doen noemen we acties.
Wat iets of iemand kan zijn noemen we toestanden.
Gedrag is de verzameling van toegestane acties.
Een actie is een verandering van de ene toestand naar de andere toestand
Acties kunnen we weergeven met behulp van een graaf. Hierbij worden toestanden
weergeven als een cirkel met in het midden de bijbehorende hoofdletter en worden acties
weergeven als een pijl met in het midden boven de bijbehorende kleine letter.
Zo’n graaf noemen we een Labeled Transition System (LST).
Stel je voor dat we van het gedrag van een lamp een graaf willen maken. Om te beginnen
bepaal je wat de begintoestand (initial state) moet zijn van de lamp. In dit geval bepaal ik dat
de begintoestand Aan is. Om dit aan te geven in de graaf tekenen we een pijl (zonder
begincirkel en zonder letter) die naar deze begintoestand (A) wijst.
,Daarna tekenen we de volgende actie. De volgende actie vind ik het uit gaan. Je tekent dan
een pijl van de Aan-toestand naar een nieuwe cirkel die de Uit-toestand (B) voorstelt. Deze
pijl geef ik als letter een u.
Een andere actie is Aan gaan. Dit kunnen we ook tekenen in de graaf. We tekenen dan een
pijl van de Uit-toestand naar de Aan-toestand. Deze pijl geef ik als letter een a.
,Er blijven nog een actie (kapot gaan) en een toestand (kapot) over. Deze tekenen we ook in
de graaf. We tekenen een cirkel die de toestand kapot (Z) weergeeft. Omdat een lamp zowel
wanneer hij aan als uit is kapot kan gaan, tekenen we twee pijlen: een pijl van de Aan
toestand naar de kapot toestand en een pijl van de uit toestand naar de kapot toestand.
De actie ‘kapot gaan’ is een speciale actie. Deze actie is een actie die zomaar kan
gebeuren. We noemen zo’n actie een stille actie. Bij pijlen van een stille actie schrijven we
geen letter bij. De andere acties waarbij die bewust worden gedaan noemen we zichtbare
acties.
, De graaf is bijna klaar. Het enige wat we nog moeten doen is het weergeven wat de laatste
toestand is. Deze toestand mag je zelf bepalen. Dit doen we door nog een cirkel te zetten
om de gekozen eindtoestand (final state) te zetten. Je kunt ook meerdere eindtoestanden
hebben.
Een LTS met een eindig aantal toestanden en acties wordt eindige toestand LTS (finite-state
labelled transition system) genoemd. Een finite-state labelled transition system met een
begintoestand en toegestane toestanden wordt een eindige toestandsautomaat genoemd
(finite state automaton).
Niet alleen kunnen we het gedrag met behulp van graven weergeven, maar ook met
wiskundige notaties. Je formaliseert dan een labeled transitie systeem. Je schrijft dan:
L = (S, A, →, so (of si), Ω).
- S staat voor alle toestanden. Dit schrijf je zo: S = {A, B, C, D, etc.}.
- A staat voor alle zichtbare acties. Dit schrijf je zo: A = {a, b, c, d, etc}. Deze bevat
alleen unieke letters (en niet dat als je een actie meerdere keren ziet dat je die
meerdere keren opschrijft).
- → staat voor alle mogelijke overgangen. Deze schrijf je zo: → = {(A, a, B), (B, b, C),
(C, τ, D), etc.}. Deze bevat wel de overgangen met de stille acties. Door te kijken
hoeveel verschillende soorten silent acties in de overgangen zijn, kun je weten
hoeveel silent acties er zijn.
- so staat voor de begintoestand. Er is altijd maar één begintoestand. Deze schrijven
we zo: so (of si) = A.
- Ω staat voor de eindtoestand(en). Omdat er meerder eindtoestanden zijn, schrijven
we de eindtoestand(en) in accolades. Dit schrijf je zo: Ω = {Z}
- Een stille actie wordt aangeduid met τ. De stille actie wordt ook wel een τ-stap
genoemd.
Het aantal zichtbare acties kun je vinden door het aantal letters die A bevat op te tellen. Het
aantal toestanden vind je door alle knooppunten op te tellen.
Een geformaliseerde LTS bestaat dus uit:
- S: een set van toestanden
- A: een set van zichtbare acties
- →: een overgang tussen toestanden, die bepaalt hoe het systeem van de ene
toestand naar de andere overgaat. → bevat elementen van de vorm (S, a, Z), waarbij
S de huidige toestand is, a de uitgevoerde actie is en Z de resulterende toestand is.
