Контрольная работа по "Основам трансляции"

 

Решение задач  по курсу «Основы трансляции».

 

1. Дана грамматика. Построить вывод заданной цепочки.

 

a) S ® T | T+S | T-S b) S ® aSBC | abC

T ® F | F*T  CB ® BC

F ® a | b  bB ® bb

Цепочка   a-b*a+b  bC ® bc

cC ® cc

Цепочка   aaabbbccc

 

Решение:

а)

S®T-S®F-S®F-T+S®F-F*T+S®a-b*T+S®a-b*a+b

   1        2        3             4                5                6 

Правила, которые  использовали:

1) S ® T-S

2) T ® F

3) S ® T+S

4) T ® F*T

5) F ® a | b

6) S ® T; T ® F; F ® a | b

б)

S ® aSBC®aaSBCBC ®aaSBBCC ®aaabCBBCC ®aaabBCBCC

    1            2                    3                   4                       5

®aaabBBCCC ®aaabbbCCC ®aaabbbcCC®aaabbbccc

6                        7                       8                    9

Правила, которые использовали:

1) S ® aSBC 

2) S ® aSBC

3) CB ® BC

4) S ® abC

5) CB ® BC

6) CB ® BC

7) bB ® bb

8) bC ® bc

9) cC ® cc

 

2. Построить все сентенциальные формы для грамматики с правилами:

S ® A+B | B+A

A ® a

B ® b

Решение:

Сентенциальные формы:

A+B®a+B

A+B®A+b

B+A®b+A

B+A®B+a

 

3.  К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

 

a) S ® APA 

P ® + | -  

A ® a | b

Решение:

Данная грамматика относиться ко 2-типу (контекстно-свободный)

Язык: L={a+a, a-a, b+b, b-b, a-b, a+b, b-a, b+a} это пример конечного языка, состоящего из восьми цепочек.

 

b) S ® aQb | e

Q ® cSc

Решение:

Данная грамматика относиться к 3-типу (автоматный)

   Язык: L={(a)ⁿ,(c)²ⁿ,(b)ⁿ| n>=1} это пример языка содержащего бесконечное количество цепочек.

 

c) S ® 1B 

B ® B0 | 1

Решение:

Данная грамматика относиться ко 2-типу (контекстно-свободный)

     Язык: L={ цепочки из 0 и 1 с числом 1 на один больше} это пример языка содержащего бесконечное количество цепочек.

 

d)  S ® A | SA | SB 

A ® a 

          B ® b

Решение:

Данная грамматика относиться к 2-типу (контекстно-свободный)

   Язык: L={ любые цепочки из a и b | a≥1} это пример языка содержащего бесконечное количество цепочек.

 

 

4.  Построить грамматику, порождающую язык :

1. L = { aⁿ b^m | n, m >= 1}

Решение:

R₁: S®aSb|ab; G₁={{a,b},{S},S,R₁}

R₂: S®AB, A®aA|a, B®Bb|b; G₁={{a,b},{S,A,B},S,R₂}

 

2. L = { acbcgc | a, b, g - любые цепочки из a и b}

Решение:

R₁: S®AcAcAc, A®aA | bA | B, B® a | b; G₁={{a,b,c},{S, A, B },S,R₁}

 

3. L = { aⁿ b^m | n ¹ m ; n, m >= 0}

R₁: S®ASb , Sb®a | ε, A®a , AS®b | ε ; G₁={{a,b},{S, A},S,R₁}

 

 

4. L = { (a^2m b^m)ⁿ | m >= 1, n >= 0}

Решение:

R₁: S®aaAbS | ε, A®aaAb | ε ; G₁={{a,b},{S, A},S,R₁}

 

5. L = { ^ | n >= 1}

Решение:

R₁: S®aaAaa ^ , A®aAaa | ε ; G₁={{a},{S, A},S,R₁}

 

6. L = { | n >= 1}

Решение:

R₁: S®aA , aA®aaAa, A®ε ; G₁={{a},{S, A},S,R₁}

 

7. L = { | n >= 1}

Решение:

R₁: S®aaaA , A®aaA, aA®ɛ ; G₁={{a},{S, A},S,R₁}

 

 

5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

 

b) S ® Ab

A ® Aa | ba

Решение:

Данная грамматика относиться к 2-типу (контекстно-свободный)

   Язык: L={ baⁿb | n≥1 } это пример языка содержащего бесконечное количество цепочек.

 

c) S ® 0A1 | 01 

0A ® 00A1  

A ® 01  

Решение:

Данная грамматика относиться к 1-типу (контекстно-зависимый)

   Язык: L={ цепочки из 0 и 1 с  одинаковым числом 0 и 1 } это пример  языка содержащего бесконечное количество цепочек.

 

d) S ® AB

AB ® BA

A ® a

B ® b

Решение:

Данная грамматика относиться ко 1-типу (контекстно-зависимый)

Язык: L={ab, ba} это пример конечного языка, состоящего из двух цепочек.

 

e) S ® A | B 

A ® aAb | 0  

B ® aBbb | 1

Решение:

Данная грамматика относиться ко 2-типу (контекстно-свободный)

   Язык: L={ aⁿ 0 bⁿ | aⁿ 1 b²ⁿ | n≥0 } это пример языка содержащего бесконечное количество цепочек.

 

f) S ® 0A | 1S

A ® 0A | 1B

B ® 0B | 1B | ^

Решение: 

Данная грамматика относиться к 2-типу (контекстно-свободный)

Язык: L = {a^ | a Î {0,1}⁺} это пример языка содержащего бесконечное количество цепочек.

 

g) S ® 0S | S0 | D 

D ® DD | 1A | e  

A ® 0B | e  

B ® 0A | 0

Решение: 

Данная грамматика относиться к 2-типу (контекстно-свободный)

Язык: L = {a | a Î {0,1}^*} это пример языка содержащего бесконечное количество цепочек.

 

h) S ® 0A | 1S | e

A ® 1A | 0B

B ® 0S | 1B

Решение:

Данная грамматика относиться к 2-типу (контекстно-свободный)

   Язык: L={ цепочки из 0 и 1 } это пример языка содержащего бесконечное количество цепочек.

 

i) S ® SS | A 

A ® a | bb  

Решение:

Данная грамматика относиться к 0-типу (рекурсивно-перечислимый)

Язык:  L = { aⁿ | a Î {a,b}⁺, n≥1}  это пример языка содержащего бесконечное количество цепочек.

 

j) S ® AB^

A ® a | cA

B ® bA

Решение:

Данная грамматика относиться к 3-типу (автоматный)

Язык: L={ (c^mbacⁿa^ | m≥0, n≥0 } это пример языка содержащего бесконечное количество цепочек.

 

k) S ® aBA | e 

B ® bSA 

AA ® c

Решение:

Данная грамматика относиться к 1-типу (контекстно-зависимый)

Язык: L={ (ba)ⁿcⁿ | n≥0 } это пример языка содержащего бесконечное количество цепочек.

 

l) S ® Ab | c

A ® Ba

B ® cS

Решение:

Данная грамматика относиться к 2-типу (контекстно-свободный)

Язык: L={ c^m(ba)ⁿ | m=n+1 } это пример языка содержащего бесконечное количество цепочек.

 

6. Эквивалентны ли  грамматики с правилами :

 

а) S ® AB и S ® AS | SB | AB

A ® a | Aa A ® a

B ® b | Bb B ® b

 

b) S ® aSL | aL и S ® aSBc | abc

L ® Kc cB ® Bc

cK ® Kc bB ® bb

K ® b

Решение:

а)  Неэквивалентны (почти эквивалентны) 

б) Эквивалентны (так как порождают один и тот же язык)

 

7. Построить КС-грамматику, эквивалентную грамматике с правилами:

 

а) S ® aAb b) S ® AB | ABS

aA ® aaAb  AB ® BA

A ® e  BA ® AB

A ® a

B ® b

 

Решение:

а)  G={{a,b},{A,S},S,R}

R: S®aAb

A®aAb | ε

б) G={{a,b},{A,B,S},S,R}

R: S®aAb

A®aAb | ε

aAb®bAa

 

8. Построить регулярную  грамматику, эквивалентную грамматике  с правилами:

 

а) S ® A | AS b) S ® A.A

A ® a | bb  A ® B | BA

B ® 0 | 1

Решение:

а)  G={{a,b},{A,B,S},S,R}

R: S®A|AS|BS|B

A®a

B®bb

б) G={{a,b},{A,B,S},S,R}

R: S®A.A

A®0 | 1 | 0A | 1A