Lecture Formal methods in software engineering - Lecture 30 - TRƯỜNG CÁN BỘ QUẢN LÝ GIÁO DỤC THÀNH PHỐ HỒ CHÍ MINH
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (632.87 KB, 10 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
<b>Formal Methods in SE</b>
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
<b>OSI reference model</b>
Application
Presentation
Session
Transport
Network
Data link
Physical
7
6
5
4
3
2
1
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>
<b>Language (AsmL)</b>
<b>AsmL</b> is a language for modelling the <b>structure</b>
and <b>behaviour</b> of digital systems
<b>AsmL</b> can be used to faithfully capture the
abstract structure and step-wise behaviour of
any discrete systems, including very complex
ones such as:
</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>
<b>Abstract State</b>
An AsmL model is said to be abstract because it
encodes only those aspects of the system’s structure
that affect the behaviour being modelled
<i><b>The goal</b></i> is to use the minimum amount of detail
that accurately reproduces (or predicts) the
behaviour of the system
<i><b>Abstraction</b></i> <i><b>helps</b></i> us reduce complex problems into
manageable units and prevents us from getting lost in a
sea of details
</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>
<b>Turing Machine</b>
An <b>abstract state machine</b> is a particular
kind of mathematical machine, like the
Turing machine<b> (TM)</b>
But unlike a TM, <b>ASMs</b> may be defined a
very <b>high level of abstraction</b>
</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>
<b>State transitions</b>
The behaviour of a <b>machine</b> (its run) can always
be depicted as a sequence of <b>states</b> linked by
<b>state transitions</b>
• Moving from state A to state B is a
state
transition
paint in green
paint in red
</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>
<b>Configurations</b>
Each state is a particular <b>“configuration”</b> of
the machine
The <b>state</b> may be simple or it may be very
large, with complex structure
But no matter how complex the state might
be, <b>each step</b> of the machine’s operation can
be seen as a <b>well-defined transition</b> from
</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>
<b>Evolution of state variables</b>
paint in green
paint in red
A
B
We can view any machine’s state as a dictionary of
<b>(Name, Value)</b>
pairs, called <i>state variables</i>
</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>
<b>Evolution of state variables</b>
<b>Names </b>are given by the machine’s symbolic
vocabulary
<b>Values</b> are fixed elements, like numbers and
strings of characters
The
run of a machine
is a
series of
states and state transitions
that
results form applying operations
</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>
<b>Example</b>
<i>Diagram shows the run of a machine that models how orders might be </i>
<i>processed</i>
S<sub>1</sub>
Mode = “Initial”
Orders = 0
Balance = £0
Initialise Process All Orders
S<sub>3</sub>
Mode = “Final”
Orders = 0
Balance = £500
S<sub>2</sub>
Mode = “Active”
Orders = 2
Balance = £200
Each transition operation:
• can be seen as <sub>the result of invoking the machine’s </sub>
control logic on the current state
</div>
<!--links-->
