Читайте также:
|
|
Vocabulary V of language L is specified as V = {#, *, 4..8, a..f}. The chains w Î L(V) have the following syntactical construction: each chain must start with the symbol ‘#’, then there must be a sequence of symbols ‘4..8’, then there may be a sequence of symbols ‘a..f’ or a symbol ‘*’. The chain must end with the symbol ‘#’.
1. Formal definition of language L(V) with the help of Normal Backus Forms, syntactical Virt diagrams and finite-state machines.
1) Normal Backus Forms
<w>::= # <a> {<b>}01 #
<a>::= { <digit> }
< digit >::= 4|5|6|7|8
<b>::= { <letter> } | *
<letter>::= a|b|c|d|e|f
2) Syntactical Virt diagrams
Pic. 3.1 Formal definition with the help of syntactical Virt diagrams
3) Finite-state machine
А = < Q, S, d, q, F >, where Q – not an empty set of states,
S – set of output signals,
d – set of transition functions,
q – initial state,
F – set of final states.
Pic. 3.2 Set of transition functions in a graphical representation
Q = {q0, q1, q2, q3, q4, q5 }
q = { q0 }
F = { q5 }
B = { 4, 5, 6, 7, 8 }
C = { a, b, c, d, e, f }
D1 = { # }
D2 = { * }
S = P(B) È P(C) È P(D1) È P(D2)
d:
(q0, D1) ® q1
(q1, B) ® q2
(q2, B) ® q2
(q2, D2) ® q3
(q2, C) ® q4
(q2, D1) ® q5
(q3, D1) ® q5
(q4, C) ® q4
(q4, D1) ® q5
Q S | q0 | q1 | q2 | q3 | q4 |
D1 | q1 | Serror | q5 | q5 | q5 |
D2 | Serror | Serror | q3 | Serror | Serror |
В | Serror | q2 | q2 | Serror | Serror |
С | Serror | Serror | q4 | Serror | q4 |
Serror – Syntactical error
Pic. 3.3 Set of transition functions in a table representation
2. Writing of a program specification of a scanner, which recognizes chains of language L(V) or informs of a mistake.
Pic. 3.4 Step 1 | Pic. 3.5 Step 2 |
Pic. 3.6 Step 3 |
Pic. 3.7 Step 4
Pic. 3.8 Step 5
Pic. 3.9 Step 6
Pic. 3.10 Step 7
Pic. 3.11 Step 8
Pic. 3.12 Step 9
Pic. 3.13 Step 10
Дата добавления: 2015-07-10; просмотров: 71 | Нарушение авторских прав