[07.02.11] Лекция №1 (Конспекты - Теория формальных языков)

Лекция №1 [07.02.11]

Алфавит, слово, язык

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

syn – вместе, taxis – порядок, строй

Семантика – сопоставление словам некоего смысла.

Semanticas – обозначающий

Прагматика – те цели, которые ставит перед собой носитель данного языка, формируя на этом язsrt понимание.

pragmatria – деятельность

Алфавит – V – конечно непустое множество. Элементы: буквы и символы.

,

,

Слово (цепочка) – в алфавите V – произвольный кортеж из , где

- пустое слово; - один символ; - 2 символа;

если , то - количество символов в слове;

Язык в алфавите V – произвольное непустое подмножество:

язык - множество всех подмножеств множества

Соединение слов:

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

1) объединение , объединение множеств;

2) соединение

, при этом, понятно, что

Полукольцо всех языков

1) - ассоциативность операции ;

2) - коммутативность операции ;

3) , так как - нулевой элемент;

- коммутативный моноид

4) - ассоциативность операции ;

5) , так как

- моноид

6) - дистрибутивность операции ;

7) - аннулирующее свойство нуля;

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

Порождающие грамматики

Классическим способом определения языков является определение их через порождающие грамматики или грамматики Хомского.

Грамматика , где

V – терминальный алфавит;

N – нетерминальный алфавит ( );

S – стартовая аксиома;

P – множество правил вывода ( ), (мы примем P конечным);

,

Буквы V – терминалы (терминальные символы)

Буквы N – нетерминалы (нетерминальные символы)

Вхождение слова - это такая упорядоченная тройка слов , что , где:

u – левое крыло вхождения;
v – правое крыло вхождения;

x – основа вхождения;

= 1)

2)

Вхождение с наименьшей длиной левого крыла – главное вхождение.

Вхождения и слов и в одно и то же слово не пересекаются, если существуют такие слова и (возможно, пустые), что или

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

На множестве цепочек можно вывести бинарное отношение непосредственной выводимости.

Если из входит в цепочку , то говорят, что это правило применимо к данной цепочке.

Реф. транз. (вот я насокращал, твою мать) замыканием будет

,

Вывод в грамматике - конечная или бесконечная последовательность слов , в которой для любого , если существует.

, - длина вывода.