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

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра ТК
Тема:

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

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

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

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

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

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

Количество символов в цепочке называют длиной цепочки.

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

двух цепочек символов –

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

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

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

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

Обращение цепочки α обозначается как α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) – множеством предложений этого языка.

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

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

слов (словарный запас) языка.

Слово или лексическая единица (лексема) языка

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

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

Семантика языка – это раздел языка, определяющий значение предложений языка.

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

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

формальными и естественными языками.
Способы задания языка

решить следующие задачи:
определить множество допустимых символов языка – решается

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

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

Для решения используются другие подходы:

изложить смысл программы, написанной на языке программирования,
на другом языке, более понятном тому, кому адресована программа;

использовать для проверки смысла некоторую «идеальную машину»,
которая предназначена для выполнения программ,
написанных на данном языке.