Языки и цепочки символов

записанных один за другим.

Цепочки символов обозначаются греческими буквами: α, β, γ.

Цепочка – это необязательно некоторая осмысленная последовательность символов.
Последовательность «ааааббббвввв, гггддд, …, кккк» – тоже пример цепочки символов.

Для цепочки символов важен состав
и количество символов в ней,
а также порядок символов в цепочке.

Цепочки «а» и «аа», а также «аб» и «ба» – это различные цепочки символов.

Цепочки символов α и β равны (совпадают), α=β, если они имеют один и тот же состав символов, одно и то же их количество и одинаковый порядок следования символов в цепочке.

Количество символов в цепочке называют длиной цепочки.
Длина цепочки символов α обозначается как |α| (если α=β, то и |α|=|β|).

цепочек символов –
это дописывание второй цепочки в конец первой.

Конкатенация цепочек α и β обозначается как αβ

пример:
α=«ВА», а β=«СЯ»,
то αβ= «ВАСЯ»

операция конкатенации не обладает свойством коммутативности
∃ α и β, такие, что αβ≠βα
операция конкатенации обладает свойством ассоциативности
(αβ)γ =α(βγ);

обращение цепочки – это запись символов цепочки в обратном порядке.

Обращение цепочки α обозначается как αR

пример:
α=«ВАСЯ», то αR=«ЯСАВ»

справедливо следующее равенство ∀α, β: (αβ)R =βRαR

итерация (повторение) цепочки n раз, где n∈N, n>0 –
это конкатенация цепочки самой с собой n раз.

Итерация цепочки α n раз обозначается как αn

справедливы следующие равенства
∀α: α1 = α, α2=αα, α3=ααα, ... и т. д.

Пустая цепочка символов – это цепочка, не содержащая ни одного символа.

Пустую цепочку обозначают греческой буквой λ.

Для пустой цепочки справедливы следующие равенства:
1. |λ|=0;
2. ∀α: λα=αλ=α;
3. λR=λ;
4. ∀n≥0: λn=λ;
5. ∀α: α0=λ.

правил, устанавливающих способы комбинации этих символов между собой для записи осмысленных текстов.

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

Цепочка символов α является цепочкой над алфавитом V: α(V),
если в нее входят только символы, принадлежащие множеству символов V.

Для любого алфавита V пустая цепочка λ может как являться, так и не являться цепочкой λ(V).

Язык L над алфавитом V: L(V) – некоторое счетное подмножество цепочек конечной длины из множества всех цепочек над алфавитом V.

Если V – некоторый алфавит, то:
V+ – множество всех цепочек над алфавитом V без λ;
V* – множество всех цепочек над алфавитом V, включая λ.
Справедливо равенство: V* = V+ ∪ {λ}.

Цепочку символов, принадлежащую заданному языку, часто называют предложением языка, а множество цепочек символов некоторого языка
L(V) – множеством предложений этого языка.

– является чисто формальным и на практике не применяется;

– указанием способа порождения цепочек языка (заданием грамматики языка) предусматривает некоторое описание правил, с помощью которых строятся цепочки языка;

– определением метода распознавания цепочек языка – предусматривает построение некоторого логического устройства (распознавателя) – автомата, который на входе получает цепочку символов, на выходе выдает ответ: принадлежит или нет эта цепочка заданному языку.

(словарный запас) языка.
Слово или лексическая единица (лексема) языка – это конструкция, которая состоит из элементов алфавита языка и не содержит в себе других конструкций.

Синтаксис языка – это набор правил, определяющий допустимые конструкции языка.
Синтаксис определяет «форму языка» – задает набор цепочек символов, которые принадлежат языку.

Семантика языка – это раздел языка, определяющий значение предложений языка.
Семантика определяет «содержание языка» – задает значение для всех допустимых цепочек языка.

Лексическими единицами русского языка являются
слова русского языка, а знаки препинания и пробелы представляют
собой разделители, не образующие лексем.
Лексическими единицами алгебры являются числа,
знаки математических операций,
обозначения функций и неизвестных величин.
Лексическими единицами в языках программирования
являются ключевые слова, идентификаторы,
константы, метки, знаки операций;
в них также существуют и разделители
(запятые, скобки, точки с запятой и т. д.).

и естественными языками.

Способы задания языка