Задачи по курсу «Основы трансляции»

Язык: 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} это пример языка содержащего бесконечное количество цепочек. 

 

 

start="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₁}

d.  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₁} 

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

Решение:

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

9. L = {a^3ⁿ+1 ^ | n >= 1}

Решение:

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

6. L = {a^n² | n >= 1}

Решение:

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

7. L = {a^n³+1 | 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            

    aA → aaAb          

    A → e                  

    A → a

    B → b

Решение:

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

R: S→aAb

A→aAb | ε

 

b) S → AB | ABS

   AB → BA

   BA → AB

Решение:

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

R: S→aAb

A→aAb | ε

aAb→bAa 

 

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

 

а) S → A | AS    

   A → a | bb         

   B → 0 | 1

Решение:

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

R: S→A|AS|BS|B

A→a

B→bb

 

b) S → A.A

   A → B | BA

Решение:

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

R: S→A.A

A→0 | 1 | 0A | 1A