Загрузка...

ОПЕРАЦИИ НАД СТРОКАМИ


1. Операция конкатенации строк (соединение строк).
Пусть заданы строки принадлежащие множеству над алфавитом .
Тогда любую строку или можно представить в виде последовательности знаков, где .
Тогда есть конкатенация строк и .

Свойства операции конкатенации.
Пусть существуют строки принадлежащие множеству над некоторым алфавитом .
1. Конкатенация строк с пустым знаком (пустой строкой).

2. Не коммутативность операции конкатенации.

Пример. Пусть существуют две строки , тогда , . Из примера видно что , так как строки не равны.

3. Ассоциативность операции конкатенации.

Пример. Пусть существуют строки , тогда ,
Из примера видно, что , так как строки равны.

4. Строка – есть конкатенация знаков.

Пусть задана произвольная строка , представленная в виде конкатенации трех строк , каждая из этих строк принадлежит множеству над некоторым алфавитом . Тогда:
— ПРЕФИКС,
— ПОДСТРОКА,
— СУФИКС.

Определение. ФОРМАЛЬНЫМ ЯЗЫКОМ над алфавитом называется произвольное подмножество универсального множества , то есть

Пример. Пусть задан алфавит . Определим язык над алфавитом как множество двоичных чисел и представим эти числа в следующем виде:
, тогда — есть язык чисел от 0 до 7.

Операции над формальными языками.

Пусть заданы три языка
1. Конкатенация языка с пустым знаком.
, где операцию конкатенации для языков определим как множество строк таких, что , то есть

Пример. Пусть существует два языка , тогда — язык заданный перечислением.
2. Некоммутативность конкатенаци языков.

3. Ассоциативность конкатенации языков.

4. Конкатенация языка с пустым множеством.

5. Замыкание Клини. Для произвольного языка , заданного над некоторым алфавитом , существует некоторый язык называемый ЗАМЫКАНИЕМ КЛИНИ, такой, что замыкание Клини есть объединение всевозможных степеней языков , где — есть конкатенация языка с самим собой раз.

То есть
, где , .
ТЕМА 1.2. ФОРМАЛЬНЫЕ ГРАММАТИКИ.

Формальные системы.

1. Зафиксируем некий конечный алфавит . Сразу можно сказать, что данный алфавит порождает универсальное множество строк. .
2. Определим элементарные формулы, то есть строки универсального множества , которые заведомо принадлежат формальной системе.
3. Зададим аксиомы, то есть правила, позволяющие из элементарных формул получить произвольную строку формальной системы.
4. Зададим правила вывода, которые позволяют с помощью индукции получать новые строки (формулы) путем применения некоторых операций над ранее полученными строками или формулами.

Пример: Рассмотрим формальную систему – двухполюсную схему.
1. Определим алфавит .
2. -элементарные формулы двухполюсной системы.
3. Пусть — некоторые двухполюсные схемы. Тогда можно получить двухполюсную схему как .
Изобразим данные схемы:
Если есть двухполюсные схемы :

Тогда могут быть построены следующие схемы:

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

Получим .
Изобразим эти двухполюсные схемы:

Замечание. Произвольная строка в алфавите может не оказаться двухполюсной схемой.
Пример.
Замечание. Все известные математические системы являются формальными.

Пример. Арифметика натуральных чисел, булева алгебра.

Загрузка...