Международная стандартизация телекоммуникаций. Язык спецификаций и описаний SDL. Язык MSC. Лекция 3

Основная литература
Л1. Гольдштейн Б.С. Системы коммутации. Учебник для ВУЗов. 2-е издание, доп. и испр.//СПб.: BHV-2004.
Л2. Гольдштейн Б.С. Сигнализация в сетях связи. Том 1. 4-е издание. СПб.: BHV, 2005.

Изложение этого материала в:
[Л1]. Параграф 1.7
[Л2]. Параграф 2.3

Язык описаний и спецификаций SDL.
Язык MSC (Message Sequence Chart).
Язык TTCN (Tree and Tabular Combined Notation).
Язык ASN.1.

Элементы теории спецификаций ПО
Различные способы задания языков спецификаций:
Грамматики
Конечные автоматы
Спецификация должна быть конечным
Должен существовать алгоритм, за конечное число шагов проверяющий принадлежность некоторой входной спецификации
Наиболее распространенные формализмы для задания языков: грамматики, регулярные выражения, конечные и магазинные автоматы, машины Тьюринга

Конечные автоматы
Конечный автомат – это пятерка
M = (Q, Σ, δ, q0, F), где
Q – конечное множество состояний
Σ – конечное множество допустимых входных символов
δ – функция перехода
q0 из Q – начальное состояние
F – множество заключительных состояний

Детерминированные конечные автоматы
Автомат называется детерминированным, если множество δ(q, a) содержит не более одного состояния для любых q, a. Если δ(q, a) всегда содержит ровно одно состояние, то автомат называется полностью определенным.
Цепочка w допускается автоматом M, если существует последовательность шагов, приводящая нас по этой цепочке в заключительное состояние автомата
Язык распознается конечным автоматом, если им распознается каждое слово языка
Удобная форма записи конечных автоматов – диаграммы переходов

Недетерминированные и конечные автоматы
Любому недетерминированному автомату соответствует детерминированный автомат, определяющий тот же самый язык, причем известен метод конструирования эквивалентного конечного автомата
Таким образом, классы языков, задаваемых недетерминированными и детерминированными конечными автоматами, совпадают
Конечные автоматы – удобный формализм, так как их легко моделировать программно

Минимизация конечного автомата
Как найти автомат, эквивалентный данному, с минимальным числом состояний?
Алгоритм минимизации конечного автомата выглядит так:
Вначале мы удаляем все недостижимые состояния
Затем разбиваем множество всех достижимых состояний на классы эквивалентности неразличимых состояний
Из каждого класса эквивалентности мы берем только по одному представителю

План:
SDL-система
SDL-блок
SDL-процесс
Синтаксис и семантика языка SDL
Примеры

SDL состояния
INPUT
OUTPUT
SDL-диаграмма

Изложение этого материала в:
[Л1]. Параграф 9.4.
[Л2]. Параграф 2.1, 2.2 и 2.3

Блок обработки исходящего вызова
OTLOC CAS U.21

Сигналы С1.1, передаваемые в сторону линейного тракта от процесса OTLOC при исходящем соединении по СЛ, ЗСЛ

Сигналы С1.2, принимаемые в OTLOC со стороны линейного тракта при исходящем соединении по СЛ, ЗСЛ

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

SDL-диаграмма процесса OTLOC CAS U.21

Изложение этого материала в:
[Л1]. Параграф 8.2
[Л2]. Параграф 3.2