Тема 4: свойства контекстно-свободных и автоматных языков.

1. Теорема об общем виде цепочек КС-языков и слов из него.

2. Определение операций над языками.

3. Операции над автоматными языками.

4. Операции над КС-языками.

5. Операции над контекстными языками.

6. Выводы для практики.

7. Неоднозначность контекстно-свободных грамматик.

1. Теорема об общем виде цепочек КС-языков (теорема о разрастании).

Для любого КС-языка Lсуществует такое натуральное числоp>0 что для любой цепочки, принадлежащей языкуL, длина которой большеp, существует хотя бы один вариант разбиения этой цепочки на 5 частей такой что выполняется условие теоремы.

Доказательство: в качестве pрассмотрим максимальную длину цепочки, полученную бесповторным деревом вывода. Каждый нетерминал используется 1 раз.

Sαβ²jφ²µ € L, в общем виде:αβⁱjφⁱµ € L

αAµ

βφ

y

Следствие 1: Для любого автоматного языкаLсуществует такое натуральное числоp, что для любой цепочки ψ €L, |ψ|>pсуществует хотя бы один вариант разбиения этой цепочки на три части такой что выполняется условие теоремы.

С учётом особенностей автоматных грамматик, положив часть цепочек ψ и µ, равные пустым цепочкам (см. теорему о КС-языках), получим доказательство следствия.

Следствие 2: язык цепочек видаxⁿyⁿz^w,n=(1,∞) нет ни одного варианта, удовлетворяющего условию теоремы.

При p=3, ψ =xxyyzz

x(1) = α,x(2) =β,y(1) =j,yz=φ,z= µ

или x(1) = α,x(2) =β,yy=j,z(1) =φ,z(2) = µ

xxxyyzyzz/€L

Максимальное число, которе можно получить из повторного дерева вывода: p=2.

xⁿyⁿ,n>1ψxxyy

x(1) = α,xy=β,y(2) =j

или x(1) = α,x(2) =β,yy=j

xxyxyy/€L

Следствие 3: любой конечный язык является автоматным.

Доказательство: если в качестве самой длинной цепочки взять L, то ни одна из цепочек языка не удовлетворяет условию теорему, а значит теорема верна.

Следствие 4: язык арфметических выражений не является автоматным языком.

Доказательство аналогично предыдущему. Парное количество чего-то и вложенность циклов – это контекстно-свободный язык.

Следствие 5: языки программирования в общем случае не являются КС-языками (но являются контекстными).

Например, каждая процедура имеет одинаковое число параметров в каждом месте где она упоминается.

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

На практике идентификатора обрабатываются на этапе лексического анализа, а контроль за их использованием выполняется в виде семантических процедур. Аналогично с описанием процедур.

2. Определение операций над языками.

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

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

1. Объединение: L=L₁⋃L₂= { α | α €L₁vα €L₂}

2. Пересечение: L=L₁⋂L₂= { α | α €L₁л α €L₂}

3. Разность: L=L₁\L₂= { α | α €L₁л α /€L₂}

4. Дополнение: L=L₁–L₂= { α | α €L₁vα €L₂}

5. Конкатенация: L₁®L₂= { α =βj|β€L₁,j€L₂}

6. Итерация: L* = {φ* |φ€L}

7. Обращение: L^R = {φ^R|φ€L}L= {abc,bm,aca}

8. Подстановка: L_1aL₂ – подстановка в первый язык вместо терминального символа «a» любой цепочки второго языка:

   1. L₁ = {cab, al}

   2. L₂ = {a, b}

   3. L^L2_1a = {cab, cbb, al, bl}

Задания к контрольной:

1. Составление автоматных грамматик.

2. Составление контекстно-свободных грамматик.

3. Программа-анализатор.

4. Конечные автоматы.

3. Операции над автоматными языками.

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

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

Последние две операции рассматривать не будем. Все остальные рассматриваются на графе.

1. Операция объединения.

a

S₁

S

S₂

A₂

C₂

F₂

D₂

B₂

b

A₁

C₁

D₁

B₁

F₁

F

В операции объединения выполняется индексация нетерминалов обеих грамматик, добавляются вершины SиF. дуги, идущие изS₁иS₂дублируются и направляются из вершиныS. Аналогично дублируются дуги, идущие вF­₁иF₂и направляются вF.F­₁иF₂удаляются вместе с входящими в них дугами.S₁иS₂можно удалить, если отсутствуют петли и возвраты в эти вершины.

2. Операция конкатенации: после индексации нетерминалов обеих грамматик выполняется слияние вершин в вершину F₁иS₂.

   S₁

   A₁

   C₁

   F₁

   D₁

   B₁

   

   S₂

   A₂

   C₂

   F₂

   D₂

   B₂

   

S

A₁

B₁

C₁

D₁

F

Операция итерации: все дуги, идущие в F, дублируются и направляются вS.

Операция обращения: расщепляем SнаS’ иS’’ (если есть петли), получив вершину, в которую не будет ничего входить – будут только исходящие дуги. Стрелки ставим в обратном направлении.

S’

A₁

B₁

C₁

D₁

S

F

S

A₁

B₁

C₁

D₁

F

При наличии возвратов и петель для Sвыполняется операция расщепления исходной вершины на две.S’ дублирует дуги, исходящие изS’’. После этогоS’ становитсяF,FстановитсяSи меняется ориентация всех дуг на противоположные.

Операция обращения: берётся столько экземпляров автоматных грамматик, сколько символов, вместо которых происходит подстановка:

S₁^’’

A₁

C₁

F₁

D₁

B₁

S₀

S₂^’’

A₂

C₂

F₂

D₂

B₂

S₁^’

S₂^’

F₀

A₀

C₀

D₀

B₀

Грамматика, в которую выполняется подстановка, индексируется нулём. Каждый экземпляр, в который подставляется грамматика, индексируется от 1 до i, гдеi– число буквAвL₁. Если подставляемая грамматика имеет циклы или возвраты в начальные вершины, для каждого экземпляра выполняется операция расщепления начальной вершины. После этого выполняется слияние вершиныS_i’ с вершинами грамматикиG₁, из которых исходят дуги, помеченныеA. АналогичноF_iи вершины, в которые входят дуги, помеченныеA. После этого дуги, помеченныеAграмматикиG₁, исключаются.

Операция пересечения выполняется не на графах, а на грамматике:

G₁ = <V_N1, V_T1, S₁, R = {A₁  aB₁}>

G₂ = <V_N2, V_T2, S₂, R = {A₂  aB₂}>

G₁ ⋂ G₂ = <V_N1 ⋂ V_N2, V_T1 ⋂ V_T2, S₁ ⋂ S₂, R₁ ⋂ R₂ = {A₁  aB₁ ⋂ A₂  aB₂}>

G₁: S₁  aB₁ и B₁  cF₁ | αF₁

G₂: S₂  aK₂ | cK₂ и K₂  cF₂

G₁ ⋂ G₂: <S₁S₂>  a<B₁K₂> и <B₁S₂>  c<F₁K₂> - тупик, можно убрать и <B₁K₂>  c<F₁F₂>.

_{12 октября 2013 г.}

Практика №3.

Задание 1: Опишите словами множество состояний автоматов:

\	A	B	C
0	B	B	C
1	A	C	C
	0	0	1

\	A	B	C
0	B	C	C
1	C	B	C
	0	1	0

\	A	B	C	D
0	B	D	C	D
1	C	B	D	D
	0	1	1	0

\	A	B	C	D
0	B	D	C	D
1	A	C	D	D
	0	0	1	0

Автоматы детерминированные, так как в каждом состоянии только один символ.

Решение…

Для 1 таблицы:

1­ⁿ0ⁿ1 – произвольное число нулей и единиц, которых может не быть.

m=(0, ∞).

n=(0, ∞).

Для 2 таблицы:

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

n=(0, ∞).

Для 3 таблицы:

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

10^m

m=(0, ∞).

n=(0, ∞).

Для 4 таблицы:

1ⁿ010^m

m=(0, ∞).

n=(0, ∞).

Рассмотрим недетерминированные автоматы:

\	A	B	C
0	A,B		C
1		B,C
	0	0	1

\	A	B	C
0	B
1		C,A
	0	0	1

\	A	B	C	D
0	B	C,D	B
1		B
	0	0	0	1

Для 1 таблицы:

0­ⁿ1^m0^k– произвольное число нулей и единиц, которых может не быть.

m=(1, ∞).

n=(1, ∞).

k=(0, ∞).

Для 2 таблицы:

0 ⁿ1ⁿ– произвольное число нулей и единиц, которых может не быть.

n=(1, ∞).

Для 3 таблицы:

Из нуля можем попасть в B(0), изB– вCиD(00), оттуда – вB(0 или 00).

0(1ⁿ(00)^m)^k0

n=(0, ∞).

m=(0, 1).

k=(1, ∞).

Задание 2: Построить конечный автомат с входным алфавитом (0,1), который допускает следующее множество цепочек:

1. Все возможные цепочки, включая пустую.

2. Все цепочки кроме пустой.

3. Ни одной входной цепочки (автомат будет работать и ничего не распознавать).

4. Одну входную цепочку: 1,0,1.

5. Две входные цепочки: 0,1 и 0,1,0,0.

6. Входные цепочки, начинающиеся с 0 и заканчивающиеся на 1.

7. Все цепочки, состоящие из нулей и не содержащие единиц.

8. Все цепочки, содержащие в точности 1,1,1. Нулей может быть сколько угодно.

9. Все цепочки, в которых перед и после каждой единицы стоит 0.

1.

\	A
0	A
1	A
	1

2. Aне допускает обрыв цепочки.

\	A	B
0	B	B
1	B	B
	0	1

3. Распознаёт пустую цепочку.

\	A
0
1
	0

4.

\	A	B	C	D
0		C
1	B		D
	0	0	0	1

5.

\	A	B	C	D	E
0	B		D	E
1		C
	0	0	1	0	1

7.

\	A	B	C
0	B	B
1		B,C
	0	0	1

8.

\	A	B	C	D
0	A	B	C	D
1	B	C	D
	0	0	0	1

9.

\	A	B	C	D
0	A,B		D	A
1		C
	1	0	0	1

Задание 3:Построить детерминированный автомат, эквивалентный следующему недетерминированному.

\	1	2	3
a	2,3		1
b	2	1	3
	0	0	1

В 1 столбец вставляется новое состояние, включающее все начальные состояния НДА (если на пересечении строк и столбцов имеется несколько состояний и у которого несколько начальных состояний).

\	{1}	{2,3}	{2}	{1,3}	{1,2,3}
a	{2,3}	{1}		{1,2,3}	{1,2,3}
b	{2}	{1,3}	{1}	{2,3}	{1,2,3}
	0	1	0	1	1

0 - без обрыва цепочки, 1 - допускает обрыв цепочки.

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

Заменяем:

{1} – 1, {2,3} – 2, {2} – 3, {1,3} – 4, {1,2,3} – 5

Самостоятельно привести недетерминированные в детерминированные.

______________________________

Несколько слов по построению анализатора:

if<условие>then<оператор 1> [ELSE<оператор 2>];

<условие> ::= {<идентификатор>|<константа>} <оператор отношения <,>,= и т.п.> {<идентификатор>|<константа>}

<оператор 1> ::= <идентификатор>:= {<идентификатор>|<константа>} <арифметическая операция> {<идентификатор>|<константа>}

Граф:

0 if0условие0then0оператор 10;0else0оператор 20;(F).

Борьба с пробелами:

0 _1 состояние_1 состояние (пока есть пробелы)условие…

0 идентификатор или константа0оператор отношения0идентификатор или константа⊥

_{26 октября 2013 г.}

Практика №3.

SaA|aB|bB|bD

AaB|aS|bD

BcS|cB|bD|bF’

DdD|dB|bB|bA|aF’|cF’

F’  ⊥F

<S>  a<AB>|b<BD>

<A>  a<BS>|b<D>

<B>  c<BS>|b<DF’>

<D>  d<BD>|b<AB>|a<F’>|c<F’>

<F’>  ⊥<F>

<AB>  a<BS>|b<DF’>|c<BS>

<BD>  c<BSF’>|b<DF’AB>|d<BD>|a<F’>

<BS>  a<AB>|b<BDF’>|c<BS>

<DF’>  a<AB>|b<BDF’>|c<BS>

<DF’>  d<BD>|b<AB>|b<F’>|c<F’>|⊥<F>

<BSF’>  a<AB>|b<BDF’>|c<BS>|⊥<F>

<DF’AB>  a<BSF’>|b<DF’AB>|d<BD>|c<BSF’>|⊥<F>

<BDF’>  c<BSF’>|b<DF’AB>|d<BD>|a<F’>|c<F’>|⊥<F>

<S> = S, <AB> = A, <BD> = B; <BS> = C; <DF> = D; <BSF’> = E; <DF’AB> = G; <BDF’> = H; <F’> = F’; <F> = F.

S  aA|bB

A  aC|bD|cC

B  cE|bG|dB|aF’

C  aA|bH|cC

D  dB|bA|aF’|cF’|⊥F

E  aA|bH|cC|⊥F

G  aE|bG|dB|cE|⊥F

H  cE|bG|dB|aF’|cF’|⊥F

Задача №2: устранить и исключить тупики из следующих правил…

S  aBcD|kLMp

B  cLpDq|pDc|f

D  fDr|f

F  a|b

L  fM

M  Lk|pMLc

K  rF

Шаг 1.

X₀ = V_T

X₁ = {B,D,F}

X₂ = {B,D,F,S,K}

X₃= {B,D,F,S,K}

L,M– циклический тупик внешнего типа, поскольку изLмы никуда не попадаем кромеLиMи также изM– только вLиM.

Шаг 2:

DfDr|f

Fa|b

KrF

Y₀= {S} – множество нетерминаловS.

Y₁= {S,B,D} – множество нетерминалов, в которые можно попасть не более чем за 1 шаг изS.

Y₂= {S,B,D}

K,F– тупики внутреннего типа.

Задача №3.

SAB|BC|kL

BBS|AL

CQS|dC

MxN|yM|zS|h

A aA|bL|c

L  cB|f

Q  qQ|aC

N  xC|a|bM

Шаг 1.

x₀ = {V_T}

x₁= {M,A,L,N} – вMесть терминалh.

x₂ = {M,A,L,N,S,B}

x₃ = {M,A,L,N,S,B}

Q,C– циклический тупик внешнего цикла.

Шаг 2.

S  AB|BC|kL

B  BS|AL

A aA|bL|c

y₀ = {S}

y₁ = {S,A,B,L}

y₂= {S,A,B,L}

M,N– циклический тупик внутреннего типа.

Задача №4: устранить аннулирующее правило из следующих грамматик:

S  aCDe|Kp

C  dSa|ε

D  dD|DD|a|fK|ε

K a|b

Шаг 1.

x₀ = ε;

x₁ = {C,D}

x₂ = {C,D}

S € x₂  ε € L

S  aCDe|aDe|aCe|ae|Kp

C  dSa

D  dD|d|DD|D|a|fK

Ka|b

Задача №5: устранить аннулирующее правило из следующих грамматик:

S  aSbS|bSaS|ε

Шаг 1.

x₀ = ε

x₁ = {S}

S € x₁

ε € α

S  S₁|ε

S₁  aS₁BS₁|bS₁aS₁|abS₁|aS₁b|ab|baS₁|bS₁a|ba

Задача №6: устранить аннулирующее правило из следующих грамматик:

S  ABC

B  CC|a

A  BB|ε

C  AA|b

Шаг 1.

x₀ = ε

x₁ = {A}

x₂ = {A,C}

x₃ = {A,C,B}

x₄ = {A,C,B,S}

Шаг 2.

Делается замена и добавляется правило SS₁.

S₁  ABC|AC|AB|BC|A|B|C

B  CC|a|C

A  BB|B

C  AA|b|A

Задача №7: устранить цепные правила из грамматики.

S  S+T|T

T  T*F|F

F  (S)|a

Шаг 1.

S  S+T|T*F|(S)|a – ответ.

TT*F|(S)|a– подставляем вместоF: (S)|a

F(S)|a

Задача №8: найти приведённую грамматику, эквивалентную следующей…

S  A|B

B  D|E

A  C|D

C  S|a|ε

DS|b

ES|c|ε

Приведённой является грамматика, в которой нет тупиковых, обобщённых и цепных правил.

Шаг 1.

x₀=V_T

x₁= {C,D,E} – там, где есть терминальные символы.

x₂ = {C,D,E,B,A}

x₃ = {C,D,E,B,A,S}

Нет тупиков внешнего типа. Изо всех правил можно перейти в другое.

Шаг 2.

y₀= {S}

y₁= {A,B} – куда попадаем изSне более чем за 1 шаг.

y₂= {S,A,B,C,D,E}

Нет тупиков внутреннего типа аналогично.

Шаг 3.

x₀=ε

x₁= {C,E}

x₂ = {C,E,A,B}

x₃ = {C,E,A,B,S}

x₄ = {C,E,A,B,S,D}

S € x₄  ε € L.

S  a|b|c| ε.

_{9 ноября 2013 г.}

Практика №4.

Задание №1: устранить левую рекурсию.

S  AB

A  Aa|Ab|d|c

B  qK|rB|Bf|Bg

K  aS|b

S  AB

A  dA’|cA’

A’  aA’|bA’|ε

B  qKB’|rBB’

B’  fB’|gB’|ε

k  aS|b

Свойства языков.

Задание №2: доказать что язык автоматный.

{0ⁿ10ⁿ},n>= 1;

ψ=αβ¥,p= 3;

αβ^j¥ €α

ψ= 00100, 00 + 10 + 0

Размножаем: 00 (α) + 1010 (β²) + 0 (¥)

Или: 00 (α) + 11 (β²) + 00 (¥)

Значит не существует ни одного варианта, удовлетворяющего условию теоремы, и язык не автоматный.

Задание №3: {aⁱbⁱc^j},i,j>= 1;j<=i; - доказать что цепочка не принадлежит КС-языку. Для КС-языка нужно разбить цепочку уже на 5 частей

Рассмотрим цепочку, у которой i=j:

αβ¥φµ:

ψ = aabbcc,a(α) +ab(β) +b(¥) +c(φ) +c(µ):

Размножаем: a + abab + b + cc + c € L

ψ = aabbcc, a (α) + a (β) + b (¥) + b (φ) + cc (µ):

aa + bb + b + cc + c € L

Задание №4: выполнить все допустимые операции над следующими автоматными грамматиками:

G₁: S  aA|bB|c

A  aS|a

S  B

G₂: S  aA

A  bA|bC

C  aA|cS|d

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

2. Конкатенация

3. Итерация для 1 грамматики

4. Обращение для 2 грамматики

5. Подстановка первой вместо второй

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

7. Первые пять выполняем как графы на страницах 21-25.

8. Шестая операция: ищем общие нетерминалы между каждыми группами:

9. <S₁, S₂>  a <A1, A2> - тупик // из S₁ или S₂ попадаем в A1 A2.

10. <S₁, A₂>  b <B₁, A₂> | b <B₁, C₂>

11. <S₁, C₂>  a <A₁, A₂> | c <F₁, s₂>

12. <A₁, S₂>  a <S₁, A₂> | a <F₁, C₂>

13. <A₁, C₂>  a <S₁, A₂> | a <F₁, A₂>

14. <B₁,A₂>b<F₁,A₂> |b<F₁,C₂>

15. Ответ: G₁в объединении сG₂дают пустое множество.

16. Грамматики предшествования Вирта – к следующей

21. Лекция №5.

22. Контекстно-свободные языки замкнуты относительно операций объединения, конкатенации, итерации, обращения и подстановки, и не замкнуты относительно операций пересечения, дополнения и разности (автоматные языки замкнуты относительно всех операций).

23. Имеются языки L₁(G₁) и L₂(G₂).

24. G₁ = (V_T1, V_N1, R₁, S₁)

25. G₂ = (V_T2, V_N2, R₂, S₂)

1. Объединение: G₁ v G₂ = (V_T1 v V_T2, V_N1 v V_N2 v {S}, R₁ v R₂ v {S  S₁|S₂}, S)

2. Конкатенация: G₁ ® G₂ = (V_T1 v V_T2, V_N1 v V_N2 v {S}, R₁ v R₂ v {S  S₁S₂}, S)

3. Итерация: G₁* = (V_T1, V_N1 v {S}, R₁ v {S  S₁S|S₂}, S)

   1. S  SS₁|S₁

   2. S  SS|S

4. Обращение: G₁^R= (V_T1,V_N1,R₁^R,S₁), гдеR₁^R– правила с обращёнными правыми частями правил вывода.

26. R₁ A  α A  abCAm|ba

27. R₁^R A  α^R A  maCba|ab

5. G₁^G2_a = ((V_T1\{a}) v V_T2, V_N1 v V_N2, (R₁ \ {A  αaβ}) v {A  αS₂β}, S₁)

28. Если имеются L­₁= {a^jb^jcⁱ}L₁⋂L₂= {aⁱbⁱcⁱ}не КС-язык

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

31. Операции над контекстными языками:

35. 7 декабря 2013 г.

36. Практика №7.

37. Грамматика предшествования по Флойду.

38. Выполнить разбор правильной и неправильной цепочек:

39. S  |A.B|

40. A aA|a

41. B  (B)|C

42. C  0|…|0|0C|…|9C

44. U L R

45. S | |

46. A a a

47. B (, 0|…|9 ), 0|…|9

48. C 0|…|9 0|…|9

50. S1/S2 | . a ( ) 0|…|9

51. | = <

52. . = < <

53. A > <

54. ( < = <

55. ) > >

56. 0|…|9 > > <

• - нетерминал, затем терминал