НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

1. Повторения

1.1. Слова и языки

Наша первая тема - повторения слов. Это старейший предмет, изучаемый в рамках теории формальных языков и восходящий к работе Акселя Туэ начала века. Результаты Туэ неоднократно переоткрывались в различных формах. Прежде чем обсуждать непосредственно сами эти результаты, необходимо ввести некоторые понятия и термины (они потребуются нам на протяжении всего изложения).

Алфавит ∑ - это конечное непустое множество. Буквы (символы) - элементы алфавита ∑. Слово над алфавитом ∑ - это конечная цепочка, состоящая из нуля или более букв из ∑, причем одна и та же буква может входить в слово несколько раз. Цепочка, состоящая из нулевого количества букв, называется пустым словом и обозначается λ. Таким образом λ, 0, 1, 010, 1111 суть слова над алфавитом ∑ = {0, 1}. Множество всех слов (соответственно всех непустых слов) над алфавитом ∑ обозначается ∑* (соответственно ∑+). Множество ∑* бесконечно для любого ∑. С алгебраической точки зрения ∑* и ∑+ представляют собой свободный моноид и свободную полугруппу с множеством образующих ∑.

Необходимо иметь в виду, что множество ∑, его элементы и цепочки его элементов можно с равным успехом назвать словарем, словами и предложениями соответственно. Такой подход применяется главным образом в области формального анализа естественных языков. Мы сохраняем стандартную математическую терминологию, введенную выше.

Если x и y - слова над алфавитом ∑, то их катенация xy (результат приписывания) - тоже слово над ∑. Катенация является ассоциативной операцией, и пустое слово служит единицей по отношению к ней: xλ = λx = x для всех x. Если x - слово, а i - натуральное число, то xi обозначает слово, полученное катенацией i слов, каждое из которых есть x. По определению x0 - пустое слово λ.

Длина слова x, обозначаемая |x|, есть число букв в x, причем каждая буква считается столько раз, сколько раз она входит в x. Опять же по определению |λ| = 0. Функция длины обладает некоторыми формальными свойствами логарифма: для всех слов x, y и неотрицательных целых i

|xy| = |x| + |y|, |xi| = i|x|.

Слово x называется подсловом слова y, если существуют такие слова x1 и x2, что y = x1xx2. Если при этом x1 = λ (соответственно x2 = λ), то x называется началом или префиксом (соответственно концом или суффиксом) слова y.

О подмножествах множества ∑* говорят как о (формальных) языках над ∑. Таким образом,

L1 = {a, ba, aaba, b5} и L2 = {ap|p - простое}

являются языками над алфавитом ∑ = {a, b}, причем первый конечен, а второй бесконечен. Конечный язык может быть, хотя бы теоретически, задан списком всех его слов. Подобная процедура для бесконечных языков невозможна - для их задания необходимо какое-то описание, отличное от списка. Финитными заданиями бесконечных языков в основном и занимается теория формальных языков. Различные классы финитно задаваемых языков будут рассмотрены ниже.

Используемая нами терминология может показаться несколько необычной: ведь язык должен состоять из предложений, а не из слов, как у нас. Однако, как было указано выше, это несущественно и зависит только от выбора основной терминологии, которую в случае необходимости можно изменить.

В теории языков важнейшей операцией является операция морфизма. Морфизмом называется отображение h: ∑*→Δ*, где ∑ и Δ - алфавиты, удовлетворяющее условию

h (xy) = h (x) h (y) для всех слов x, y.(1.1)

Для языков L над ∑ определим h(L) = {h(w)|w∈L}. (С алгебраической точки зрения морфизм языков есть моноидный морфизм, естественным образом продолженный на подмножества моноидов.) В силу (1.1) для задания морфизма h достаточно указать все слова h(a), где а пробегает все элементы конечного алфавита ∑.

Тройка G = (∑, h, w), где ∑ - алфавит, h: ∑*→∑* - морфизм и w - слово над ∑, называется DOL-системой. DOL-система G определяет последовательность S(G) слов над ∑:

w = h0(w), h(w) = h1(w), h(h(w)) = h2(w), ...,

а также язык L(G) = {h1(w)|i≥0}. Таким образом, DOL-система является очень простым средством задания языка. Языки, заданные с помощью DOL-системы, называются DOL-языками. Они рассматриваются в гл. 5; там же объясняется сокращение DOL.

Бесконечная последовательность элементов алфавита ∑ называется ω-словом или сверхсловом. Таким образом, ω-слово может быть отождествлено с отображением множества неотрицательных целых чисел в ∑. Очень удобным средством задания конкретных ω-слов являются DOL-системы. Именно, рассмотрим DOL-систему G = (∑, h, w), такую, что

h (w) = wx, x∈∑+, (1.2)

т. е. w - собственное начало (начало слова, не совпадающее с самим словом) слова h(w) и, кроме того, h является нестирающим (т. е. h(a)≠λ для всех a из ∑). Тогда, согласно (1.2),

h2(w) = wxh (x), h3(w) = wxh(x)h2(x)

и вообще

hi+1(w) = hi(w)hi(x) для всех i≥0.(1.3)

Равенство (1.3) показывает, что hi(w) для всех i является собственным началом слова hi+1(w). (При этом hi(x)≠λ, так как h нестирающее.) Следовательно, ω-слово α может быть определено как "предел" последовательности hi(w), i = 0, 1,2 ... . Точнее, α представляет собой ω-слово, начало которого, имеющее длину |hi(w)|, есть hi(w), i = 0, 1,2, ... . (Понятия начала и подслова естественным образом распространяются и на ω-слова. Слово x является подсловом ω-слова α, если α можно записать в виде x11, где α1 и x1 - слово и ω-слово соответственно. Если x1 = λ, то x называется началом ω-слова α.) О полученном таким образом ω-слове α говорят, что оно порождено DOL-системой G.

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru