Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Пример. Сохранив алфавиты предыдущего примера, зададим образы букв так: 2->10 и / -+11 (т. е. первые четыре
натуральных числа в двоичной записи). Тогда, например, 10 является одновременно образом буквы z и цепочки ух: расшифровка уже не является однозначной. Таким образом, {00, 01, 10, 11} — код, а {0, 1, 01, 11} — не код.
Задачей алгебраической теории кодирования является характе-ризация тех подмножеств множества X*, которые являются кодами, т. е. тех подмножеств, которые порождают свободную подполугруппу.
Заметим, что если Л— код, то полугруппу А* называют множеством сообщений.
13.3.2. Необходимое и достаточное условие кодовости
Для того чтобы Acz X* было кодом, необходимо и достаточно, чтобы выполнялось следующее условие:
(L) (У/єХ*)[(Д*/Л А* Ф 0&fA*[}A* Ф 0)=Ф/<= Л*)].
Доказательство. Вместо утверждения (L) 4Ф (Л есть код) мы докажем равносильное утверждение
(Л не есть код)
1. (Л не есть код)=ф"Л (L).
Если Л = {йь ..., os} — не код, то множество цепочек из Л*, допускающих каждая по меньшей мере два чтения, не пусто, и в этом Г л. XIII. Г омоморфизм полугрупп
213
множестве можно выделить подмножество цепочек минимальной длины. Пусть
IU = Ctii ... ain = Oii ... а,р (1)
— одна из таких цепочек. Минимальность длины т влечет за собой неравенство а,, ф а/,. Не уменьшая общности изложения, можно предположить, что
Kl ah I,
откуда
Oh = Otfi, Л є Г, |Л|#0. (2)
Из (1) и (2) следует, что
Oi2 ... Oin = hah ... atp. (3)
Из (2) вытекает, что
A'h П А' Ф 0, а соотношение (3) влечет за собой
НА* П А' Ф 0;
однако из (3) и минимальности т следует, что h^A*. Таким образом, (L) не имеет места: из допущения, что А — не код, следует «не (L)».
2. ~~і (L) =#> (А не есть код). По предположению найдутся такие
fsr, gz=A*, АєЛ', ^f=At, ft'sX',
что
gf = h, fg' = h', f<?A\
Из условия /ф.А* следует, что f не пусто; следовательно, и А не пусто и, во всяком случае, g ф h. Но из соотношений gfg' = hg' =
— gh', g Ф h следует, что А не является кодом. Глава XIV
ДОПОЛНИТЕЛЬНЫЕ СВЕДЕНИЯ ОБ АВТОМАТНЫХ ЯЗЫКАХ
§ 14.1. СТАНДАРТНЫЕ А-ЯЗЫКИ
14.1.1. Определение
Пусть Vt — терминальный алфавит. Определим язык Ks следующими условиями:
. все цепочки языка Ks начинаются с некоторой буквы, принадлежащей выделенному подмножеству I алфавита Vt (/ — множество допустимых начальных букв);
.. все цепочки языка Ks оканчиваются некоторой буквой, принадлежащей другому выделенному подмножеству J алфавита Vt (/ — множество допустимых конечных букв);
... в цепочках языка Ks не встречаются диграммы (пары стоящих рядом букв), входящие в заданное множество Дс Vt X Vt.
Пример.
VT = {a,b, c,d,f}-, I = {a,b,c}-, J = {c,f}.
Множество А запрещенных диграмм мы представим с помощью матрицы следующего вида:
Конечные буквы
Начальные буквы
Вторая буква Первая^^ буква ^v44 а Ь с f d
а 0 0 1 0 1
Ь 0 1 1 1 0
с 0 0 0 0 1
f 0 0 1 1 1
d 1 1 1 1 0
Стоящий на пересечении строки х и столбца у элемент 0 означает, что диаграмма ху запрещена, 1 —что она разрешена.
Языки, удовлетворяющие сформулированным условиям, являются А-языками; мы будем называть такие А-языки стандартными. Гл. XIV. Дополнительные сведения об автоматных языках
215
В самом деле, множество тех цепочек в Vt, которые начинаются буквой из / и оканчиваются буквой из /, может быть представлено в виде
IVT П VTJ,
а множество цепочек, содержащих запрещенные диграммы, — в виде
vt avt.
Следовательно, язык Ks представляется как пересечение:
Поскольку VT, I, J, А суть А-языки (/,/,А конечны), из результатов § 10.4 следует, что Ks есть А-язык.
14.1.2. Система уравнений, определяющая язык Ks
Пусть имеется язык Ks, заданный четверкой
(Vr, I, J, А),
где
VT = {a%\\/ = {av ..., a0j}, J = (aP), ...,
Для случая, когда некоторые буквы могут быть и начальными и конечными, положим
IflJ = (aVl, ..., aVA}.
Множество А запрещенных диграмм мы зададим с помощью функции 6(?,, (д,), такой, что
( 0, если диграмма а%а^ запрещена, б (а,, |х) = { .
11, если диграмма O^ajx разрешена.
Эта функция фактически использовалась в предыдущем пункте: ею определяются элементы матрицы запрещенных диграмм.
Построим формальный степенной ряд S, опорным множеством которого будет язык Ks- Введем сначала вспомогательные ряды Au An, где п равно числу терминальных символов Ob ..., ап.
Говоря более точно, букве ах е Vt ставится в соответствие (некоммутативный) формальный степенной ряд Атакой, что
1) все цепочки опорного множества ряда Ax можно присоединять конкатенацией справа к аъ т. е. если некоторая цепочка ряда Ax начинается буквой а^,, то диаграмма а^а^, разрешена: б (Я,, ц) = = 1;
2) цепочки опорного множества ряда Ax содержат только разрешенные диграммы;
3) всякая цепочка опорного множества ряда Ax оканчивается буквой из /. 216
Часть III. Алгебраический подход
Построим теперь систему из п + 1 уравнений; эти уравнения будут иметь в качестве первых членов S, Au ..., An соответственно.
