Cтраница 3
Заметим, что событие е, образованное пустым словом е, состоит из одного слова нулевой длины и играет вспомогательную роль в теории автоматов. Кроме события е будем также рассматривать пустое событие 0, которое состоит из пустого множества букв входного алфавита, и поэтому является частью любого события. [31]
Действительно, в силу принятого выше определения вхождения пустое слово входит во всякое слово р, причем первое его вхождение не будет иметь слева от себя ни одной буквы. Отсюда же непосредственно следует, что применение указанной подстановки к произвольному слову р переведет его в слово хр. [32]
Лемма 2.5. Пусть множество входных слов V, содержащее пустое слово, переводит автомат %, в не менее чем i 1 состояние. [33]
Можно считать, что любое слово начинается вхождением пустого слова. [34]
Считается, что всякое слово начинается простым вхождением пустого слова. Поэтому всякое слово поддается ф-ле с пустой левой частью. [35]
Иными словами, в итерацию S, кроме пустого слова, входит всякое такое слово А, которое может быть получено путем приписывания друг за другом любого конечного числа слов из S. Назовем регулярными событиями все элементарные события, а также все те события, которые могут быть получены из элементарных событий с помощью конечного числа дизъюнкций, умножений и итераций. [36]
ТЗ) удаление W, если № - - пустое слово. [37]
В частности, пустое слово переводится отображением ф в пустое слово. [38]
Итак, ( - 1) - цепъ - это пустое слово Л1, являющееся своим собственным хвостом. Она также совпадает со своим хвостом. [39]
Начальным состоянием автомата является состояние, в котором он помнит пустое слово. [40]
Полугруппа, состоящая из слов - наборов свободных образующих и пустого слова с операцией, состоящей в приписывании одного слова к другому. [41]
Поэтому задача представления событий выходными сигналами для случая событий, содержащих пустое слово, строго говоря, не имеет смысла. [42]
Описанный выше стандартный прием действительно позволяет ( с учетом сделанных замечаний относительно пустого слова) свести общую задачу синтеза автоматов к канонической задаче. Что же касается последней задачи, то она всегда имеет решение в силу предложения 4.2. Однако такое решение ( основанное на результатах § 2) не может нас удовлетворить, поскольку оно приводит к построению, вообще говоря, бесконечного автомата даже в тех случаях, когда существует дающий решение задачи конечный автомат. [43]
Если конструкция К является пустой, то считается, что ей соответствует пустое слово. Если же К непуста, то выполняют следующий процесс. [44]
Из последовательности р можно образовать, заменяя 0 на, 1 на пустое слово Л, последовательность cxg: С &... [45]