Участник:Rzakhar2/Черновик

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

Множества и операции над ними.

Множество - это совокупность, набор элементов, объединенных общими свойствами.

Бинарные операции

Основные бинарные операции, определяемые над множествами:

• пересечение:

  $A\cap B:=\{x\mid x\in A\land x\in B\}$.

• объединение:

  $A\cup B:=\{x\mid x\in A\lor x\in B\}$.

Если множества $A$ и $B$ не пересекаются, то $A\cap B=\varnothing$. Их объединение обозначают также: $A+B=A\cup B$.

• разность:

  $A\setminus B:=A\cap {\overline {B}}=\{x\mid x\in A\land x\notin B\}$.

• симметрическая разность:

  $A\triangle B\equiv A{\dot {-}}B:=$

  $(A\cup B)\setminus (A\cap B)=A\cap {\overline {B}}+{\overline {A}}\cap B=$

  $=\{x\mid (x\in A\land x\notin B)\lor (x\notin A\land x\in B)\}$.

• декартово или прямое произведение:

  $A\times B=\{(a,\;b)\mid a\in A,\;b\in B\}$.

Унарные операции

Диаграмма Венна для $(A\cap B)^{\complement }$

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

${\overline {A}}\equiv A^{\complement }:=\{x\mid x\notin A\}$.

Операция дополнения подразумевает некоторый зафиксированный универсум (универсальное множество $U$, которое содержит $A$), и сводится к разности множеств с этим универсумом:

${\overline {A}}=U\setminus A$.

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

Булеан — множество всех подмножеств:

$2^{X}\equiv {\mathcal {P}}X:=\{A\mid A\subset X\}$.

Обозначение $2^{X}$ происходит из свойства мощности множества всех подмножеств конечного множества:

$\left|2^{X}\right|=2^{|X|}$.

Булеан $2^{X}$ порождает систему множеств с фиксированным универсумом $X$, замкнутую относительно операций объединения и пересечения, то есть, образует булеву алгебру.

Приоритет операций

Последовательность выполнения операций над множествами, как и обычно, может быть задана скобками. При отсутствии скобок сначала выполняются унарные операции (дополнение), затем — пересечения, затем — объединения и разности, которые имеют одинаковый приоритет. Операции одного приоритета выполняются слева направо. При этом надо иметь ввиду, что в отличии от арифметических сложения и вычитания, для которых верно, что $(a+b)-c=a+(b-c)$, для аналогичных операций над множествами это неверно. Например, если $A=\{1,3\},B=\{1,2\},C=\{2,3\},$ то $(A\cup B)\setminus C=\{1\},$ но, в то же время, $A\cup (B\setminus C)=\{1,3\}$.

Комбинаторика

Комбинато́рика (комбинаторный анализ) — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана с другими областями математики — алгеброй, геометрией, теорией вероятностей и применяется в различных областях знаний (например, в генетике, информатике, статистической физике).

В комбинаторике размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.

Пример 1: $\langle 1,3,2,5\rangle$ — это 4-элементное размещение из 6-элементного множества $\{1,2,3,4,5,6\}$.

Количество размещений из n по k, обозначаемое $A_{n}^{k}$, равно убывающему факториалу:

$A_{n}^{k}=n^{\underline {k}}=(n)_{k}=n(n-1)\cdots (n-k+1)={\frac {n!}{(n-k)!}}={\binom {n}{k}}k!.$

В комбинаторике перестано́вка — это упорядоченный набор чисел $1,2,\ldots ,n,$ обычно трактуемый как биекция на множестве $\{1,2,\ldots ,n\}$, которая числу i ставит в соответствие i-й элемент из набора. Число n при этом называется порядком перестановки. Как синоним слову «перестановка» в этом смысле некоторые авторы используют слово расстановка.

• Число всех перестановок порядка $n$ равно числу размещений из n по n, то есть факториалу:

$P_{n}=A_{n}^{n}={\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!=1\cdot 2\cdot \dots \cdot n.$

В комбинаторике сочетанием из $n$ по $k$ называется набор $k$ элементов, выбранных из данного множества, содержащего $n$ различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Число сочетаний из $n$ по $k$ равно биномиальному коэффициенту

${n \choose k}=C_{n}^{k}={\frac {n!}{k!\left(n-k\right)!}}.$

• Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел.
• Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

Операции A* и A⁺ над множеством A

Степень множества

Нулевая степень любого множества неизменна:

$V^{0}=\left\{\varepsilon \right\}$.

Остальные степени определяются рекурсивно:

$V^{i}=V^{i-1}V=\left\{wv\left|\,w\in V^{i-1}\land v\in V\right.\right\}$, где $i\in \mathbb {N}$.

Если $V$ — множество символов

то $V^{i}$ — множество строк длиной $i$ символов, взятых из $V$.

Звезда Клини

Замыкание Клини множества $V$ есть

$V^{*}=\bigcup _{i=0}^{\infty }V^{i}$.

То есть это множество всех строк конечной длины́, порождённое элементами множества $V$.

Плюс Клини

Есть операция, аналогичная звезде Клини, — плюс Клини:

$V^{+}=\bigcup _{i=1}^{\infty }V^{i}$.

Как видим, отличается тем, что пропущено $V^{0}$, содержащее пустую строку.

Свойства

• Связь операций:
  1. $V^{+}=V^{*}V$
  2. $V^{+}=V^{*}\Leftrightarrow \varepsilon \in V$
• Идемпотентность:

$V^{*}={V^{*}}^{*}$.

• Замыкание Клини включает в себя порождающее множество:

$V\subseteq V^{*}$.

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

$\varepsilon \in V^{*}$.

• Счётность:

$\left|V^{*}\right|=\left|V^{+}\right|=\aleph _{0}\Leftarrow \varnothing \neq V\neq \{\varepsilon \}$.

Примеры

Для множества строк

{"Go", "Russia"}* = {ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}.

Для множества символов

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", …}.

Понятие символа, цепочки символов и конечного алфавита.

Алфави́т формального языка — множество атомарных (неделимых) символов какого-либо формального языка (иногда называемых буквами по аналогии с алфавитами естественных языков). Из символов алфавита формального языка строятся слова, а заданием формальной грамматики — допустимые выражения языка.

Чаще всего алфавит рассматривается как непустое конечное множество. Например, алфавит $\{\cdot ,-\}$ лежит в основе азбуки Морзе, алфавит $\{0,1\}$ — общепринятый набор символов для представления информации в компьютерах. Нотные знаки, цифры — также примеры конечных алфавитов. В некоторых случаях рассматриваются и бесконечные алфавиты, например, множество натуральных чисел $\mathbb {N}$ — простейший пример счётного алфавита (при этом натуральные числа могут быть рассмотрены и как слова над конечным алфавитом цифр).

Слово формального языка (также — цепочка, строка) — произвольная последовательность символов из данного алфавита. Число символов в слове $\alpha$ называют его длиной и обозначают $|\alpha |$. Может допускаться существование единственного слова длины 0, (пустое слово), не содержащее ни одного символа (обозначается $e$, $\varepsilon$ или $\Lambda$).

Формальный язык над конечным алфавитом

Формальный язык в математической логике и информатике — множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.

Формальный язык может быть определён по-разному, например:

• Простым перечислением слов, входящих в данный язык. Этот способ, в основном, применим для определения конечных языков и языков простой структуры.
• Словами, порождёнными некоторой формальной грамматикой (см. иерархия Хомского).
• Словами, порождёнными регулярным выражением.
• Словами, распознаваемыми некоторым конечным автоматом.
• Словами, порождёнными БНФ-конструкцией.

Формальные грамматики. Алфавиты терминальных и нетерминальных символов.

Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.

• Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.
• Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.

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

Итак, грамматика определяется следующими характеристиками:

• $\Sigma$ — набор (алфавит) терминальных символов
• N — набор (алфавит) нетерминальных символов
• P — набор правил вида: «левая часть» $\rightarrow$ «правая часть», где:
  • «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал
  • «правая часть» — любая последовательность терминалов и нетерминалов
• S — стартовый (или начальный) символ грамматики из набора нетерминалов.

Вывод

Выводом называется последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путём замены некоторой подстроки по одному (любому) из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.

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

Типы грамматик

По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):

• тип 0. неограниченные грамматики — возможны любые правила
• тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.
• тип 2. контекстно-свободные грамматики — левая часть состоит из одного нетерминала.
• тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.

Кроме того, выделяют:

• Неукорачивающиеся грамматики. Каждое правило такой грамматики имеет вид $\alpha \rightarrow \beta$, где $|\alpha |\leqslant |\beta |$. Длина правой части правила не меньше длины левой.
• Линейные грамматики. Каждое правило такой грамматики имеет вид $A\rightarrow uBv$, или $A\rightarrow u$, то есть в правой части правила может содержаться не более одного вхождения нетерминала.

Пример — арифметические выражения

Рассмотрим простой язык, определяющий ограниченное подмножество арифметических формул, состоящих из натуральных чисел, скобок и знаков арифметических действий. Стоит заметить, что здесь в каждом правиле с левой стороны от стрелки $\Rightarrow$ стоит только один нетерминальный символ. Такие грамматики называются контекстно-свободными.

Терминальный алфавит:

$\Sigma$ = {'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}

Нетерминальный алфавит:

  { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

Правила:

1. ФОРМУЛА $\to$ ФОРМУЛА ЗНАК ФОРМУЛА                (формула есть две формулы, соединенные знаком)
2. ФОРМУЛА $\to$ ЧИСЛО                               (формула есть число)
3. ФОРМУЛА $\to$ ( ФОРМУЛА )                         (формула есть формула в скобках)
4. ЗНАК $\to$ + | - | * | /                          (знак есть плюс или минус, или умножить, или разделить)
5. ЧИСЛО $\to$ ЦИФРА                                 (число есть цифра)
6. ЧИСЛО $\to$ ЧИСЛО ЦИФРА                           (число есть число и цифра)
7. ЦИФРА $\to$ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (цифра есть 0 или 1, или ... 9 )

Начальный нетерминал:

ФОРМУЛА

Вывод:

Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.

ФОРМУЛА ${\stackrel {3}{\to }}$ (ФОРМУЛА)

(ФОРМУЛА) ${\stackrel {1}{\to }}$ (ФОРМУЛА ЗНАК ФОРМУЛА)

(ФОРМУЛА ЗНАК ФОРМУЛА) ${\stackrel {4}{\to }}$ (ФОРМУЛА + ФОРМУЛА)

(ФОРМУЛА + ФОРМУЛА) ${\stackrel {2}{\to }}$ (ФОРМУЛА + ЧИСЛО)

(ФОРМУЛА + ЧИСЛО) ${\stackrel {5}{\to }}$ (ФОРМУЛА + ЦИФРА)

(ФОРМУЛА + ЦИФРА) ${\stackrel {7}{\to }}$ (ФОРМУЛА + 5)

(ФОРМУЛА + 5) ${\stackrel {2}{\to }}$ (ЧИСЛО + 5)

(ЧИСЛО + 5) ${\stackrel {6}{\to }}$ (ЧИСЛО ЦИФРА + 5)

(ЧИСЛО ЦИФРА + 5) ${\stackrel {5}{\to }}$ (ЦИФРА ЦИФРА + 5)

(ЦИФРА ЦИФРА + 5) ${\stackrel {7}{\to }}$ (1 ЦИФРА + 5)

(1 ЦИФРА + 5) ${\stackrel {7}{\to }}$ (1 2 + 5)

Пораждающие и распознающие грамматики.

Порождающие грамматики — не единственный вид грамматик, однако наиболее распространенный в приложениях к программированию. В отличие от порождающих грамматик, аналитическая (распознающая) грамматика задает алгоритм, позволяющий определить, принадлежит ли данное слово языку. Например, любой регулярный язык может быть распознан при помощи грамматики, задаваемой конечным автоматом, а любая контекстно-свободная грамматика — с помощью автомата со стековой памятью. Если слово принадлежит языку, то такой автомат строит его вывод в явном виде, что позволяет анализировать семантику этого слова.