Алфавиты, слова, языки, алгоритмические проблемы

Цели и задачи

1. Ввести подходящий формализм для работы с текстами -

Формальный язык

Алфавитом называется любое непустое конечное множество.
Каждый элемент алфавита называется символом.
Алфавит

Примеры стандартных алфавитов

∑bool={0, 1} - логический (Булевый) алфавит
∑lat={a, b, c, …,

Алфавит и строки

Будем использовать алфавит из двух букв
∑={a, b}
Строки (слова)
a, ab,

w = a1a2…an v = b1b2…bm
w = abba v = bbbaaa
Конкатенация: Длина строки:
wv

Операции над строками

Пустая строка:
Строка, не содержащая букв: λ |λ| = 0
λw =

Префиксы и суффиксы:
Строка: abba
Префиксы: Суффиксы: w = uv
λ abba u - префикс
a bba v - суффикс
ab ba
abb a
abba λ

Операции над

Итерация: w0 = λ
(abba)2 = abbaabba = ab2a2b2a (abba)0 = λ
Звезда Клини:
∑*

Плюс Клини:
∑ + = ∑* - λ ∑+ = {a, b,

Операции над языками

Обращение
LR {wR: w ϵ L}
{ab, aab, baba}R = {ba, baa, abab}
Конкатенация

Итерация
{a, b}3 = {a, b} {a, b} {a, b} = {aaa,

Звезда Клини (замыкание)
L* = L0 U L1 U L2 U …

Операции

Плюс Клини (положительное замыкание)
L+ = L1 U L2 U … =

Грамматики определяют языки, является ли данное предложение правильным предложением данного языка.
Пример:

<предложение> => <подлежащее> <сказуемое> <дополнение> =>
=> <существительное> <глагол> <наречие> =>
=> Птица

Обозначения

Пример формальной грамматики

G = {V, T, S, P}
V = Множество нетерминальных символов
T =

Определение:
Для грамматики G с начальным символом S
L(G) = {w: S =>

Любая программа (алгоритм) A выполняет отображение:
A: ∑1* → ∑2*
входы представлены как

Проблема принадлежности

Оптимизационная проблема

U = {∑I, ∑O, L, M, cost, goal)
∑I – входной

Сложность по Колмогорову

Колмогоровская сложность объекта есть мера вычислительных ресурсов, необходимых для