I.Формальные языки и грамматики

I.1. Цепочки символов

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

a d

b c

Обозначение цепочек α,β,γ.

Для цепочки символов имеет значение три фактора:

1.состав символов

2. их количество

3. порядок символов

<<a>> и <<aa>>,<<аб>> и <<ва>> - различные цепочки символов.

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

│α│ - длина цепочки символов отображающая таким образом │α│

Если α=β,то │α│=│ β │

I.2. Операции над цепочками символов

1)Конкатенация (сложение, объединение 2ух цепочек)

Дописывание 2ой цепочки в конце 1ой

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

Выполняется следующем образом:

если α=аб,β=вг,то αβ=абвг

Цепочку символов можно разбить на несколько подцепочек разными способами произвольным образом

Например: можно представить в виде комбинации цепочек

γ=абвг α=аб β=вг (γ= αβ)

или

υ=а и ω=ввг (γ= υа)

2)Если некоторую цепочку разбить на составляющие ее подцепочки,а затем заменить одну из подцепочек на произвольную, то в результате получится новая цепочка символов. Такое действие называется заменой или подстановкой.

Пример: разобьем цепочку γ=абвг на α=а, ω=б, β=вг (γ= α ω β) и выполним подстановку

υ =аба вместо подцепочки ω и получаем γ = аабавг(γ’= α υ β)

3)Обращение цепочки α α^R

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

Если α= <<абвг>>, то α^R = <<гвба>>

α , β : (α β)^R = β^R α^R

4)Итерация (повторение цепочки n-раз, где n ∈ N и n > αⁿ)

Это действие (n ∈ N) конкатенация цепочки самой собой n раз.

Для этого действия справедливы следующие равенства :

α : α¹=а, α²=аа …

При n=0 результатом будет пустая цепочка, которая не содержит ни одного символа (обознач. λ или [е,ε])

Для пустой цепочки справедливы следующие равенства

│ λ │=0

α: λ α = α λ= α

λ^R = λ

n=0 : λⁿ = λ

α: α⁰ = λ

I.3. Понятие языка

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

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

Цепочка символов α является цепочкой над алфавитом

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

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

V⁺ – это множество всех цепочек над алфавитом V

V^* – это множество всех цепочек над алфавитом λ(V)

V^* = V⁺ ∪ { λ }

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