# Exercise 1

A->BB->CCB->CCCC
За първата буква 2 варианта, втората буква 2 варианта, ...
2 * 2 * 2 * 2 = 16

# Exercise 2

A->BB->CCB->CCCC
думи с дължина 0: 1
думи с дължина 1: 2
думи с дължина 2: 4
думи с дължина 3: 8
думи с дължина 4: 16
1 + 2 + 8 + 4 + 16 = 1 + 10 + 20 = 31

# Exercise 3

ПРЕЧКА: .^n регулярен ли е?

a. НЕ, балансиране, (^n )^n
b. ДА, ((()*, (^2n
c. ДА, няма цикличност, т.е. краен
d. ДА, a*b
e. ДА, ba*
f. НЕ, a^2n b^n
g. ДА, (aab)*
h. ДА, (aab)+

# Exercise 4

a. ДА, S->A->B-> C->B+C->C+C
b. НЕ, S->A->C->D->B-|
                 -|
              ->B+C-|
           ->B-|
c. НЕ, S->A->D-|
           ->B-|
           ->C-|
d. ДА, S->A->C->D->A
e. НЕ, C->1C не може да породи
f. ДА, C->C+B

# Exercise 5

a. ДА, А->Sb->Aab|db
b. ДА, S->Aa|d->Sba|d
c. НЕ, ЛЯВА РЕКУРСИЯ, A->Aab
d. НЕ, РАЗЛИЧЕН ЕЗИК, S->dAa->da

# Exercise 6

E->E*E->5*E->5*E+E->5*3+E->...    3.
                  ->5*E+4->...    5.
 ->E+E->E+4->E+E+4->5*3+E+4->...  1.
           ->5*E+4                4. MISSED
      ->5*3+E->...                2.

# Exercise 7

a. да, избираме дърво 3 вместо 4
b. не, дървета 1 и 2 не се различават с това
c. да, избираме дърво 1 вместо 2 финално
d. не, никои дървета не се различават с това

# Exercise 8

a. ДА, (00)+, регулярен => безконтекстен
b. ДА, a^n b^n, не рег, да безк
c. НЕ, a^n b^n c^n, не рег, не безк
d. НЕ, 0^(n*n)
e. ДА

# Exercise 9

Г1. n++
    S->aSb->aSbb->abbb
    S->Sb->aSbb->abbb
    m=0
    k=0
    заради S->Sb

Г2. n=0
    всяко правило генерира своя си буква
    m++
    k=0
    заради S->Sa|Sb

Г3. n++
    S->SaS->SaSaS->aaS->aaa
    S->SaS->SaSaS->Saa->aaa
    m=0
    k=0
    заради S->SaS

Г4. n=0
    всяко правило генерира своя си буква
    m++
    k++
    няма правило от типа A->Ax, така че рекурсивното спускане няма да забие

=> n=2, m=2, k=1

# Exercise 10

S->A1->101
     ->1
     ->C1->01
         ->11
 ->1B->1
     ->1C1->101
          ->111
Думи: 101, 1, 01, 11, 111 ; 5
Дървета: 7

# Exercise 11

a. ДА
b. ДА
c. НЕ, не може да генерира int-int+int
d. НЕ, не може да генерира int*int+int
e. ~~НЕ, не може да генерира int*int+int~~
  MISSED ДА

# Exercise 12

Първо S->A
Сравнява всички нули, стига до 1ца, връща се
Второ S->B
Сравнява първата нула с 1ца, връща се
Трето S->0S
Сравнява един път и почваме пак от началото

За 001:
3 + 1 + 1 +   2 + 1 + 1 +     1 + 1 = 11
n + 2     +   n-1 + 2   +     n-2 + 2   
2*n + n + n-1 + n-2 ...
2*n + n*n - (0+1+2...)
(2+n)*n - (0+n-1)*n/2 = n* (2+n - n/2 +1/2) = n* (2.5 + n/2) = n* (5/2 + n/2) =

(5 + n) * n / 2 - 1 = O(n^2)

За 0001:
4 + 1 + 1   +    3 + 1 + 1    +  2 + 1 + 1   + 1 + 1 = 18 - 1