An example of task accomplishment

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>}₀¹ #

<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 = {q₀, q₁, q₂, q₃, q₄, q₅ }

q = { q₀ }

F = { q₅ }

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:

(q₀, D1) ® q₁

(q₁, B) ® q₂

(q₂, B) ® q₂

(q₂, D2) ® q₃

(q₂, C) ® q₄

(q₂, D1) ® q₅

(q₃, D1) ® q₅

(q₄, C) ® q₄

(q₄, D1) ® q₅

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

S_error – 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