1.Операции над словами и языками. Понятие грамматики и грамматического вывода.

В={b₁, b₂,…b_m} - некоторое конечное множество букв.

Слово в алфавите В – произвольная конечная последовательность символов (символы могут повторяться).

α (альфа) = b₁, b₂,…,b_n

| α | - длина слова, число символов (| α | = n).

λ – пустое слово (не содержит ни одной буквы).

| λ |=0 // пустое слово принадлежит множеству всех слов В*.

| α |_b – число вхождений буквы b в слово α.

В* - множество всех слов в алфавите В. Это бесконечный язык, если алфавит не пустой, счетное множество.

Язык L – произвольное подмножество множества В. L включ. в В*.

Язык может быть конечным или бесконечным.

Операции над словами.

Пусть есть слово α.

1. Обращение слова α – α^R (буквы в обратном порядке), одноместная операция.

α = 010111, α^R = 111010.

2. Конкатенация обозначается α*β или αβ, двухместная операция.

α=11010, β=001, αβ=11010001.

К слову α справа дописывается слово β (склеивание, слияние, умножение).

• слова α αλ=α=λα (λ играет роль единицы).

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

Т.к. язык – это множество, над ним можно применять все теоретико-множественные операции.

1. Объединение.

L1 U L2 = {α| λ ϵ L1 или λ ϵ L2}.

2. Пересечение.

L1 ∩L2 = { α| λ ϵ L1 и λ ϵ L2}.

3. Разность.

L1\L2 = { α| λ ϵ L1 и λ не ϵ L2}.

4. Дополнение.

_

L = B*\L дополнение до множества всех слов в алфавите

Конкатенация языков.

L₀ = {λ} L¹*L²={α|α=βγ, βєL¹, γϵL²}

Используются степени языков.

L¹= L, L²= L*L¹=L*L, L³=L*L²=L*L*L,…, Lⁿ=L*L^n-1

Пример. Рассмотрим конечные языки

L¹={ab, bac}, L²={ba, ab, c}

Построим конкатенацию

L¹*L²={abba, abab, abc, bacba, bacab, bacc}

1-ая часть слов входит в язык L¹, 2-ая в L²

Операция некоммутативна

L²*L¹={baab, babac, abab,abbac,cab,cbac}

Используя операцию степени, введем операцию итерация языка.

L*=U(i=1,…,∞)Lⁱ

L⁰={λ}. т.к. λ входит в L*, итерация любого языка содержит устое слово, итерация не может быть пустым множеством (всегда есть λ).

Позитивная итерация.

Одноместная итерация

L⁺=U(n=1,…,∞)Lⁿ

Пустое слово обязательно не содержится? Нет., т.к. λ может быть в языке L, для которого строится L⁺, следовательно L⁺ содержит {λ} и L⁺ совпадает с L*.

Может быть L*=Ø? Нет, т.к.всегда есть λ.

Может быть L⁺=Ø? Да, когда L=Ø.

Грамматики.

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

G=<V_T, V_N, P, S>

V_T – алфавит терминальных символов (основных)

V_N – алфавит нетерминальных символов (вспомогательных)

P – конечное множество правил

Sϵ V_N – некоторый выделенный символ нетерминального алфавита, который называется аксиомой.

V_T∩ V_N алфавиты не пересекаются, все буквы различны.

Как применяются правила.

Если есть слово γ=α₁βα₂ и в множестве правил есть β→δ (из β следует δ) получим γ’= α₁δα_2.

И говорят, что γ’ непосредственно выводимо из γ (с помощью применения одного правила). γ => γ’.

Правило можно применять многократно. =>* - рефлексивная транзитивная выводимость.

Любое слово выводимо из себя. Рефлексивность: α =>* α, транзитивность: можно применять правило любое конечное число раз.