Алфавитом называется множество, элементы которого будем называются буквами или символами

Алфавиты будем обозначать заглавными латинскими буквами.

 

Примеры алфавитов:

A = {а, б, в, …. },

В = { Å, r, J },

C = {0, 1}

D = {|}.

Любая конечная последовательность букв алфавита называется словом.

Приведем примеры слов.

В алфавите B словами будут следующие последовательности букв:

Å, Å r, rrr, J rr J.

В алфавите D можно построить следующие слова:

|, ||,

,

В любом алфавите можно построить бесконечное множество слов. Однако не любая последовательность букв образует правильное слово с точки зрения данного языка. Например, в алфавите A последовательность букв «карова» не является правильным словом с точки зрения русского языка. Обозначим множество всех слов, которые можно построить в данном алфавите, через. Языком называется подмножество L множества всех слов алфавита A:. Слова, входящие в подмножество L, называются правильно построенными словами. Связь между множеством всех слов алфавита и множеством слов, образующих язык, показана на рис. 6. Рис. 6. Множество правильно построенных слов Возникает задача задания подмножества L правильно построенных слов. Если язык состоит из конечного числа слов, он может быть задан путем их перечисления. Такой перечень слов называется словарем. Но если число слов в языке бесконечно или даже просто очень велико, задача задания языка становится непростой. Здесь возможны два подхода. 1. Задание правил построения правильно построенных слов.

Совокупность правил, позволяющих строить правильные слова, называется грамматикой.

2. Задание правила распознавания правильно построенных слов. Такое правило является алгоритмом, на вход которого подается слово, а на выходе появляется ответ «да», если слово входит в язык, или «нет», если слово не входит в язык.

Слова могут объединяться в более сложные конструкции – предложения.

Предложением называется конечная последовательность правильно построенных слов.

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

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

Каждому правильному предложению языка приписывается некоторый смысл.