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

ФОРМАЛЬНЫЕ ЯЗЫКИ, АВТОМАТЫ И ГРАММАТИКИ

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

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

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

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

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

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

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

Определение. Алфавитом T называется конечное непустое множество. Его элементы называются символами (буквами).

Определение. Словом (цепочкой, строкой) в алфавите T называется конечная последовательность элементов из T.

Пример. Если , то 1, 100, 101, 11011 и 0001 – строки символов из Т.

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

Пример. Пусть T ={ a, b }. Длина слова baaa в этом алфавите:

| baaa | = 4.

Определение. Слово, не содержащее ни одного символа, называется пустымсловом и обозначается ε.

| ε | = 0.

Множество всех слов в алфавите T обозначается T ^*.

Множество всех непустых слов в алфавите T обозначается T ⁺.

Следовательно, Т * = Т + È {e}.

Пример. Пусть T ={ a, b }. Тогда

T ^* ={ ε, a, b, aa, ab, ba, bb, aaа,....},

T ⁺ ={ a, b, aa, ab, ba, bb, aaa, aab,....}.

Пример. Если Т ={0, 1}, то

Т * = {e, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}.

Определение. Если a= … и b = … - строки (цепочки), принадлежащие T ^*, то цепочка

ab= … …

называется конкатенацией (или сцеплением) цепочек a и b.

Замечание. Конкатенацию иногда будем записывать с помощью символа бинарной операции : .

Для любой цепочки a всегда ae = ea = a,

т.е. если строке предшествует или следует за ней пустая строка, то в результате конкатенации получаем ту же самую строку.

Определение. n -ой степенью цепочки a (будем обозначать an) называется конкатенация n цепочек a.

a 0 = e; an = aan- 1 = an- 1 a.

Определение. (Формальным ) языком L над алфавитом T называется произвольное подмножество множества T ^*, т.е. L Í T ^*.

Пример. Если T – множество букв английского алфавита, то L – множество слов английского языка.

Если алфавит T – множество символов языка программирования, то L – множество слов этого языка.

Если Т ={0, 1}, то следующие множества являются языками:

L₁ ={0, 1, 00, 11, 000, 111, …},

,

,

Если Т ={ a, b, c }, то следующие множества являются языками:

L₁ = { acb, aacbb, aaacbbb, …},

,

,

Необходимо различать пустой язык L =Æ, не содержащий ни одного слова и язык, содержащий только пустое слово L ={ ε }¹ Æ.

Определение. Пусть . Тогда – множество всех строк, образованных конкатенацией слов из множества .

Определение. Выражением над алфавитом Т называется строка символов, которая представляет собой подмножество . Регулярное выражение состоит из символов и а для каждого элемента .

Класс регулярных выражений определяется следующими правилами:

i) Символ – регулярное выражение и для каждого символ а – регулярное выражение.

ii) если и – регулярные выражение, то , , и – регулярные выражения.

iii) Все регулярные выражения образуются по правилам i) и ii).

Каждому регулярному выражению можно сопоставить регулярные множества :

, ,

Поэтому