Автоматы, языки и грамматики.

 

Язык – это совокупность правил, построенных конструкций (предложение).

Грамматика - это совокупность следующих объектов: <V_т,V_n,I,R>=G

V_т – словарь терминальных символов, которые состоят из основных символов языка, к которым относятся буквы, цифры, знаки и неделимые конструкции языка.

V_т = {a,b,…,z}

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

V_n = {A,B,…,Z}

I – начальный символ грамматики, является элементом нетерминального словаря.

I? V_n

R – множество порожденных правил вида

φ à ψ₁, где φ и ψ – цепочки символов, которые относятся к полному словарю V_Т и V_n определенные.

V = V_т  v V_n

В φ входит хотя бы один нетерминальный символ

V_т*  - множество конечных цепочек, построенных из терминальных символов.

V*  - множество цепочек, построенных из терминалов и нетерминалов.

α, β, φ, ψ? V^* - конечные цепочки, построенные из символов общего словаря. Порождающее правило определяет подстановку, при котором последовательность φ заменяется на последовательность ψ.

Пусть есть R: φ à ψ и есть цепочка

ώ₁ = ξ₁ φ ξ₂

ώ₂ = ξ₁ ψ ξ₂

ξ₁ ξ₂  ? V* - цепочки

Тогда говорят, что ώ₂ непосредственно выводится из непосредственно выведенной из ώ₁ и обозначается

ώ₁ => ώ₂ или

n

ώ₁ => ώ₂

Предположим, что есть множество цепочек:

Ω = { ώ₁ , ώ₂, ώ₃ , …, ώ_n}

ώ₁  => ώ₂

ώ₂  => ώ₃

_…

ώ_n-1 => ώ_n и обозначается

n

ώ₁ => ώ₂

Множество конечных цепочек, которые выводятся из начального символа грамматики и которые представлены только терминальными символами называются языком порождаемой грамматикой. L(G) = { ώ: ώ? V_т* & I => ώ }

Рассмотрим примеры грамматик и языков:

1. G₁

V_т = {a, b, c}

I

V_n = {I}

R = {Iàabc}

L(G₁) = {(abc)}

2. G₂

V_т = {a, d, c}

I

V_n = {I, B, C}

R = {Iàab, BàCd, BàdC, C àc}

I => ab => aCd => acd

             => adC => adc

L(G₂) = {(acd), (adc)}

3. G₃

V_т = {a, b, e}

I

V_n = {I, A}

R = {IàaAb, aAàaaAb, Aàc}

I => aAb => ab

I => aAb => aaAbb => aaaAbbb => aaabbb

L(G₃) = {(aⁿbⁿ) n>=1}

4. G₄

V_т = {a, b}

I

V_n = {I, A}

R = {IàaA, AàbA}

I => aA => abA => abbA => …

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

Чтобы язык был не пуст в нем должно быть:

a) хотя бы одно правило вида:

η à w, w? V_т^*

*

b) I => η

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

Пример:

V_т = {a, b}

V_n = {I, A}

I

R = {I => aAb, A à aAb}

Это синтаксический разбор цепочки. Порожденная цепочка представляет собой конечные вершины дерева, которые выписываются при обходе вершин дерева против часовой стрелки. Две грамматики называются эквивалентными, если они порождают одинаковые языки.

G₃  и G₅ – эквивалентны.

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

G₆:

V_т = {a, b, с, d}

I

V_n = {I, A, B}

R = {IàAB, Aàa, Aàac, Bàb, Bàcb}

I => AB => acB => acb

I => AB => AcB => acb

Данная цепочка неоднозначна, следовательно G₆ неоднозначна.

 

Задача распознавания цепочек языка.

 

Задачей распознавания является задача определяющаяся является ли заданная цепочка порождением заданной грамматикой.

R = φàψ, где φ,ψ? V^*

ώ₁ = ξ₁ φ ξ₂ = ώ₂ = ξ₁ ψ ξ₂

ξ₁ ξ₂  ? V* - цепочки

то говорят, что ώ₂ непосредственно сворачивается в ώ₁ и обозначается ώ₁<= ώ₂ либо

 n

ώ₁<= ώ₂

Пусть задано множество цепочек

Ω = { ώ₁ , ώ₂ , ώ₃ , …, ώ_n}

ώ_n-1 < = ώ_n

…

ώ₁  <= ώ₂

говорят, что ώ_n <= ώ₁

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