Соотношения между типами языков

Систематизация грамматик и языков

Формальные грамматики можно систематизировать по типу имеющихся в их правил вывода.

Грамматика G именуется неукорачивающей грамматикой, если каждое правило из R
имеет вид a®b, где aÎ V+, bÎ V+ и |a| £ |b|.

Грамматика G именуется укорачивающей грамматикой, если каждое правило из R
имеет вид a®b, где aÎ V+, b Соотношения между типами языковÎ V*.

Иерархия Хомского

T0: Грамматика G именуется грамматикой типа 0 либо рекурсивной грамматикой, если на правила вывода не накладывается никаких ограничений (не считая тех, которые указаны в определении грамматики – a¹ #).

T1: Грамматика G именуется грамматикой типа 1 либо контекстно-зависимой (КЗ) грамматикой, если каждое правило из R имеет
вид a®b, где a = x Соотношения между типами языков1Ax2; b = x1gx2; A Î Vn; gÎ V+; x1, x2Î V*.

Грамматику типа 1 можно найти как контекстно-зависимую либо как неукорачивающую. Классы КЗ-грамматик и неукорачивающих грамматик эквивалентны. Подтверждено, что огромное количество языков, порождаемых неукорачивающими грамматиками, совпадает с обилием языков, порождаемых КЗ-грамматиками.

Т2: Грамматика G именуется грамматикой Соотношения между типами языков типа 1 либо контекстно-свободной (КС) грамматикой, если каждое правило из R
имеет вид A ®b, где A Î Vn, bÎ V+ (для неукорачивающих КС-грамматик),
либо AÎVn, bÎV* (для укорачивающих КС-грамматик).

Т3:Грамматика G именуется грамматикой типа 3 либо постоянной грамматикой, грамматикой с конечным числом состояний, если каждое правило из R
имеет вид A Соотношения между типами языков ®tB (A ®Bt) или A ® t, где A, BÎVn, tÎVt.

Грамматика с правилами типа A ®tB является праволинейной.

Грамматика с правилами типа A ®Bt является леволинейной.

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

Язык L(G) является языком типа k, если его можно обрисовать грамматикой типа k Соотношения между типами языков.

Примеры:

Грамматика G и язык L типа 0

Правила G:

S®aaCFD

F®AFB | AB

AB ®bBA

Ab®bA

AD ® D

Cb®bC

CB ® C

bCD® #

L(G) = n³ 1.

Грамматика G и язык L типа 1

Правила G:

S®aSBC | abC

CB®BC

bB®bb

bC®bc

cC®cc

L(G) = {anbncn, n³ 1}

Грамматика G и язык L типа 2

Правила G Соотношения между типами языков:

S®aQb | accb

Q®cSc

L(G) = {(ac)n (cb)n, n> 0}

Грамматика G и язык L типа 3

Правила G:

S ® A | B

A ®a | Ba

B®b | Bb | Ab

L(G) = {w | wÎ {a,b}+, где нет 2-ух рядом стоящих а}

3. Эквивалентность грамматик и языков,
соотношения меж грамматиками и языками

Грамматики Соотношения между типами языков G1 и G2 эквивалентны, если L(G1) = L(G2).

Грамматики G1 и G2 сильноэквивалентны, если L(G1) = L(G2)

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

Пример:

G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)

R1: S® 0A1 R2: S® 0S1 | 01

A® 0A1

A® #

эквивалентны, т.к. обе порождают язык Соотношения между типами языков L(G1) = L(G2) = 0n1n .

Грамматики G1 и G2 условно эквивалентны, если L(G1) È {#} = L(G2) È {#}.

(если языки, ими порождаемые, отличаются менее, чем на #).

Пример:

G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)

R1: S® 0A1 R2: S® 0S1 | #

A® 0A1

A® #

условно эквивалентны, потому что Соотношения между типами языков L(G1)=0n1n , а L(G2)= n³ 0:

L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не заходит.

Соотношения меж типами грамматик

(1) неважно какая постоянная грамматика является КС-грамматикой;

(2) неважно какая КС-грамматика является КЗ-грамматикой;

(3) неважно какая КЗ-грамматика является грамматикой типа 0.

NB Соотношения между типами языков: УКС-грамматика с правилами вида A® #, не является КЗ-грамматикой.

Соотношения меж типами языков

(1) каждый постоянный язык является КС-языком, но есть КС-языки, которые не являются постоянными (к примеру, L = anbn).

(2) каждый КС-язык является КЗ-языком, но есть КЗ-языки, которые не являются КС-языками Соотношения между типами языков (к примеру, L = anbncn).

(3) каждый КЗ-язык является языком типа 0.

NB:УКС-язык, содержащий пустую цепочку, не является КЗ-языком.

NB: Если язык задан грамматикой типа k, то это не означает, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Потому, когда молвят о языке типа k, обычно имеют Соотношения между типами языков в виду очень вероятный номер k.

Пример:

КЗ-грамматика G1 = ({0, 1}, {A, S}, R1, S) и КС-грамматика G2 = ({0, 1}, {S}, R2, S),

где

R1: S ® 0A1 R2: S ® 0S1 | 01

0A ® 00A1

A® 01

обрисовывают один и тот же язык L = L(G1) = L(G2) = 0n1n .

Язык L именуют Соотношения между типами языков КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является постоянным языком, т.к. не существует постоянной грамматики, описывающей этот язык.

Эквивалентность грамматик и языков,
соотношения меж грамматиками и языками

Грамматики G1 и G2 эквивалентны, если

L(G1) = L(G2).

Грамматики G1 и G2 сильноэквивалентны, если L(G1) = L(G2) и грамматики приписывают Соотношения между типами языков цепочкам схожие структуры составляющих.

Пример:

G1 = ({0, 1}, {A, S}, R1, S) и G2 = ({0, 1}, {S}, R2, S)

R1: S® 0A1 R2: S® 0S1 | 01

A® 0A1

A® #

эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = n>0.

Вывод цепочек в грамматиках,
неоднозначность грамматик и языков

Цепочка aÎ V*, для которой Соотношения между типами языков S Þa, именуется сентенциальной формой в грамматике G.

Вывод цепочки bÎ Vt* из S Î Vn в КС-грамматике G именуетсялевым (левосторонним), если в этом выводе любая еще одна сентенциальная форма выходит изпредыдущей подменой самого левого нетерминального знака.

Вывод цепочки bÎ Vt* из S Î Vn в КС-грамматике G именуется правым (правосторонним Соотношения между типами языков), если в этом выводе любая еще одна сентенциальная форма выходит изпредыдущей подменой самого правого нетерминального знака.

(КС – контекстно-свободная грамматика)

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

Пример:

Для цепочки a+b+a в грамматике

G = ({a, b, +}, {S, T}, T+S; T ® a , S)

можнопостроитьвыводы:

(1)S®T+S®T+T+S®T+T+T®a+T+T®a+b+T®a+b+a

(2) S®T+S®a+S®a+T Соотношения между типами языков+S®a+b+S®a+b+T®a+b+a

(3) S®T+S®T+T+S®T+T+T®T+T+a®T+b+a®a+b+a

Тут (2) – левосторонний вывод, (3) – правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в обозначенном выше смысле.

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

Дерево именуется деревом вывода (либо деревом разбора) в грамматике G, если выполнены последующие условия:

(1) любая верхушка дерева помечена эмблемой из огромного количества (VnÈVtÈ #) , при всем этом корень дерева помечен эмблемой S; листья – знаками из Соотношения между типами языков (VtÈ #);

(2) если верхушка дерева помечена эмблемой AÎVn, а ее конкретные потомки – знаками a1, a2, ... , an, где каждое aiÎ (VtÈVn), то A®a1a2...an – правило вывода в этой грамматике;

(3) если верхушка дерева помечена эмблемой AÎVn, а ее единственный конкретный потомок помечен эмблемой #, то A® # – правило вывода Соотношения между типами языков в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G:

S

T S


T S


T


a + b + a

Грамматика G именуется разноплановой, если существует хотя бы одна цепочка aÎ L(G), для которой может быть выстроено два либо более разных деревьев вывода (цепочка a имеет два либо более различных левосторонних (либо правосторонних) выводов Соотношения между типами языков).

В неприятном случае грамматика именуется конкретной.

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

Пример:

разноплановая грамматика
G = ({if, then, else, a, b}, {S}, R, S),

где R = S ® if b then S else S .

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

Но это не значит, что язык L(G) непременно разноплановый.

Неоднозначность - это свойство грамматики, а не языка, так как для неких разноплановых грамматик есть эквивалентные им конкретные грамматики.

В рассматриваемом примере различные деревья вывода подразумевают соответствие else различным then. Если условиться, что else должно соответствовать наиблежайшему к нему Соотношения между типами языков then, и поправить грамматику G, то неоднозначность будет устранена:

S ® if b then S | if b then S’ else S | a

S’ ® if b then S’ else S’ | a

Некие виды правил вывода, которые приводят к неоднозначности:

(1)A ® AA | a

(2)A ®AaA | b

(3)A ®aA | Ab | g

(4)A ®aA | aAbA | g

Пример разнопланового КС-языка:

L Соотношения между типами языков = i = j либо j = k.

Цепочки с i = j должны порождаться группой правил вывода, хороших от правил, порождающих цепочки с j = k. Но тогда, по последней мере, некие из цепочек с i = j = k будут порождаться обеими группами правил и, как следует, будут иметь по два различных дерева вывода.

Одна Соотношения между типами языков из грамматик, порождающих L, такая:

S ® AB | DC

A ®aA | #

B ®bBc | #

C®cC | #

D®aDb | #

Разумеется, что она разнопланова.

Дерево вывода можно строить нисходящим или восходящим методом.

При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для верхушки, помеченной нетерминальным эмблемой, нужно отыскать такое правило вывода, чтоб Соотношения между типами языков имеющиеся в нем терминальные знаки “проектировались” на знаки начальной цепочки.

Способ восходящего разбора состоит в том, что начальную цепочку пробуют “свернуть” к исходному символу S; на каждом шаге отыскивают подцепочку, которая совпадает с правой частью какого-нибудь правила вывода; если такая подцепочка находится, то она заменяется Соотношения между типами языков нетерминалом из левой части этого правила.

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


sootnoshenie-filosofii-s-naukoj-politikoj-iskusstvom.html
sootnoshenie-form-predvaritelnogo-rassledovaniya.html
sootnoshenie-godovih-otmetok-i-otmetok-poluchennih-v-hode-gosudarstvennoj-itogovoj-attestacii-v-2012-godu.html