[CI/H3] Finished homework

1 files changed, 60 insertions, 13 deletions

diff --git a/Year 3/Compilers, Introduction/Homework3.txt b/Year 3/Compilers, Introduction/Homework3.txt
index 73c25cc..3334443 100644
--- a/Year 3/Compilers, Introduction/Homework3.txt
+++ b/Year 3/Compilers, Introduction/Homework3.txt
@@ -19,7 +19,7 @@ A->BB->CCB->CCCC
 ПРЕЧКА: .^n регулярен ли е?
 
 a. НЕ, балансиране, (^n )^n
-b. ?, (^2n
+b. ДА, ((()*, (^2n
 c. ДА, няма цикличност, т.е. краен
 d. ДА, a*b
 e. ДА, ba*
@@ -43,17 +43,18 @@ f. ДА, C->C+B
 
 # Exercise 5
 
-a. ?
-b. ?
-c. ЛЯВА РЕКУРСИЯ, A->Aab
-d. РАЗЛИЧЕН ЕЗИК, S->dAa->da
+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->...
-                  ->5*E+4->...
- ->E+E->E+4->E+E+4->5*3+E+4->...
-      ->5*3+E->...
+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
 
@@ -67,8 +68,8 @@ d. не, никои дървета не се различават с това
 a. ДА, (00)+, регулярен => безконтекстен
 b. ДА, a^n b^n, не рег, да безк
 c. НЕ, a^n b^n c^n, не рег, не безк
-d. ?
-e. ?
+d. НЕ, 0^(n*n)
+e. ДА
 
 # Exercise 9
 
@@ -77,11 +78,28 @@ e. ?
     S->Sb->aSbb->abbb
     m=0
     k=0
-    заради S->aSb
+    заради 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
 
@@ -94,4 +112,33 @@ S->A1->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