JAG

Z OI wiki

(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
m (→7.1.2011 10:00: pouze sjednocení vzhledu zkousek)
m (→14.1.2011 10:00: úprava překlepů)
Řádka 27: Řádka 27:
=== 14.1.2011 10:00 ===
=== 14.1.2011 10:00 ===
-
  '''1)''' Je dán jazyk <math>L_1</math>: <math> \mathbf{r} = (a^*(a + b)b + b(a + b))^* </math>
+
  '''1)''' [30b] Je dán jazyk <math>L_1</math>: <math> \mathbf{r} = (a^*(a + b)b + b(a + b))^* </math>
     a jazyk <math>L_2</math>:
     a jazyk <math>L_2</math>:
   
   
Řádka 50: Řádka 50:
     d) [ 8b] Rozhodněte, zda platí <math>L_2 \subseteq L_1</math>, zdůvodněte nebo uveďte protipříklad.
     d) [ 8b] Rozhodněte, zda platí <math>L_2 \subseteq L_1</math>, zdůvodněte nebo uveďte protipříklad.
-
  '''2)''' Je dána gramatika <math>G = (N, \Sigma, S, P)</math>, kde <math>N = {S, A, B, C} ,  \Sigma = {0, 1}</math>
+
  '''2)''' [20b] Je dána gramatika <math>G = (N, \Sigma, S, P)</math>, kde <math>N = \{S, A, B, C\} </math>  <math> \Sigma = \{0, 1\}</math> a pravidly P:  
-
    a pravidly P: S -> AB, A -> AC|0, B -> BC|<math>\varepsilon</math>, C -> AS|1
+
 +
      '''S -> AB'''
 +
      '''A -> AC|0'''
 +
      '''B -> BC|<math>\varepsilon</math>'''
 +
      '''C -> AS|1'''
      
      
     a) [ 8b] Převeďte gramatiku <math>G</math> do Chomského normálního tvaru a napište co to je.
     a) [ 8b] Převeďte gramatiku <math>G</math> do Chomského normálního tvaru a napište co to je.
Řádka 57: Řádka 61:
     c) [ 6b] Ukažte, že <math>G</math> je víceznačná a popište, co to znamená.
     c) [ 6b] Ukažte, že <math>G</math> je víceznačná a popište, co to znamená.
-
  '''3)''' Je dán jazyk <math> L = \{a^n b^{n+2}  |  n > 0\} </math>
+
  '''3)''' [24b] Je dán jazyk <math> L = \{a^n b^{n+2}  |  n > 0\} </math>
      
      
     a) [12b] Sestrojte zásobníkový automat, který přijímá koncovým stavem. Pečlivě popište.
     a) [12b] Sestrojte zásobníkový automat, který přijímá koncovým stavem. Pečlivě popište.
Řádka 64: Řádka 68:
             který přijímá jazyk <math>L</math> prázdným zásobníkem.
             který přijímá jazyk <math>L</math> prázdným zásobníkem.
-
  '''4)''' Je dán jazyk <math> L = \{1^{n+1} 2 0^m 2 1^{n+1}  |  m < n\} </math>
+
  '''4)''' [24b] Je dán jazyk <math> L = \{1^{n+1} 2 0^m 2 1^{n+1}  |  m < n\} </math>
      
      
     a) [12b] Rozhodněte, zda je jazyk <math>L</math> bezkontextový. Definujte, co to je bezkontextový jazyk.
     a) [12b] Rozhodněte, zda je jazyk <math>L</math> bezkontextový. Definujte, co to je bezkontextový jazyk.
     b) [12b] Rozhodněte, zda je jazyk <math>L</math> regulární. Definujte, co to je regulární jazyk.
     b) [12b] Rozhodněte, zda je jazyk <math>L</math> regulární. Definujte, co to je regulární jazyk.
-
 
-
 
=== 7.1.2011 10:00 ===
=== 7.1.2011 10:00 ===

Verze z 14. 1. 2011, 16:15

Obsah

1. semestr 2. semestr 3. semestr 4. semestr 5. semestr 6. semestr
Povinné předměty DMA ¤ LAG
PR1 ¤ RPH		 ALG ¤ BP1 ¤ LGR
MA2 ¤ PR2		 JAG ¤ PSI ¤ SPS APO ¤ BP2 ¤ FYZ OPT SZZ - LS 2012
Inf. a poč. vědy NUM ¤ OSS DS ¤ FLP ¤ ZUI RPZ
Počítačové syst. EAM ¤ EM DSP ¤ OSD PKS ¤PSR ¤NVS
Softwarové syst. OSS ¤ SI ASS ¤ DS ¤ TUR WA1
Volitelné předměty ACM ¤ EPD ¤ ET1 ¤ FI1 ¤ HI1 ¤ HSD ¤ HT1 ¤ IA+AZK ¤ MME ¤ MMP ¤ MPS ¤ PAP ¤ PPR ¤ PRS ¤ RET ¤ SOJ ¤ UFI
Grafický minor

PGR ¤ MVR ¤ KMA ¤ MGA ¤ GRT

Info o předmětu

  • Cvičící: M. Demlová, J. Demel


Pravidla předmětu

Stránka předmětu


Studijní materiály

Velice pěkná PDF na JAG z matfyzu. http://ktiml.mff.cuni.cz/~bartak/automaty/prednaska.html

Zkoušky

14.1.2011 10:00 

1) [30b] Je dán jazyk LaTeX: L_1: LaTeX:  \mathbf{r} = (a^*(a + b)b + b(a + b))^* 
   a jazyk LaTeX: L_2:

     LaTeX: \begin{tabular}{|r|r|r|}
   \hline 
   \bf  & \bf a & \bf b \\
   \hline
   \bf in 1 & \bf 2 & \bf 4 \\
   \hline
   \bf 2 & \bf 3 & \bf 4 \\
   \hline
   \bf out 3 & \bf 4 & \bf 3 \\
   \hline
   \bf 4 & \bf 4 & \bf 4 \\
   \hline
   \end{tabular}
       pokud někdo ví jak na šipky in/out, prosím doplňte
  
   a) [10b] Sestrojte DFA LaTeX: M_1 proLaTeX: L_1, zdůvodněte, proč jazyk přijímá.
   b) [ 4b] Napište regulární výraz pro jazyk LaTeX: L_2.
   c) [ 8b] Rozhodněte, zda platí LaTeX: L_1 \subseteq L_2, zdůvodněte nebo uveďte protipříklad.
   d) [ 8b] Rozhodněte, zda platí LaTeX: L_2 \subseteq L_1, zdůvodněte nebo uveďte protipříklad.

2) [20b] Je dána gramatika LaTeX: G = (N, \Sigma, S, P), kde LaTeX: N = \{S, A, B, C\}    LaTeX:  \Sigma = \{0, 1\} a pravidly P: 

     S -> AB
     A -> AC|0
     B -> BC|LaTeX: \varepsilon
     C -> AS|1
   
   a) [ 8b] Převeďte gramatiku LaTeX: G do Chomského normálního tvaru a napište co to je.
   b) [ 6b] Generuje gramatika LaTeX: G slovo '00011', zdůvodněte.
   c) [ 6b] Ukažte, že LaTeX: G je víceznačná a popište, co to znamená.

3) [24b] Je dán jazyk LaTeX:  L = \{a^n b^{n+2}  |  n > 0\} 
   
   a) [12b] Sestrojte zásobníkový automat, který přijímá koncovým stavem. Pečlivě popište.
   b) [ 5b] Ukažte výpočet zásobníkového automatu z a) na slově LaTeX: u = a^2b^4.
   c) [ 7b] k zásobníkovému automatu z a) zkonstruujte zásobníkový automat,
            který přijímá jazyk LaTeX: L prázdným zásobníkem.

4) [24b] Je dán jazyk LaTeX:  L = \{1^{n+1} 2 0^m 2 1^{n+1}  |  m < n\} 
   
   a) [12b] Rozhodněte, zda je jazyk LaTeX: L bezkontextový. Definujte, co to je bezkontextový jazyk.
   b) [12b] Rozhodněte, zda je jazyk LaTeX: L regulární. Definujte, co to je regulární jazyk.

7.1.2011 10:00 

1) [30b] Dva regulárne výrazy:
  
   LaTeX:  \mathbf{r_1} = b^*aa^*b(a + b)^*     LaTeX:  \mathbf{r_2} = (a + b)^*b 
   
   a) [10b] Zostrojte DFA LaTeX: M_1 pre reg. výraz LaTeX: \mathbf{r_1} (jazyk LaTeX: L_1) a DFA LaTeX: M_2 pre reg. výraz LaTeX: \mathbf{r_2} (jazyk LaTeX: L_2).
   b) [10b] Zostrojte DFA LaTeX: M pre rozdiel jazykov LaTeX: L = L_1 - L_2
   c) [ 5b] Automat LaTeX: M redukujte
   d) [ 5b] Napíšte regulárny výraz odpovedajúci automatu LaTeX: M

2) [25b] Daný je jazyk LaTeX:  L = \{0^n 1^m 2^{n+m} | n \ge 0, m > 0\} 

   a) [13b] Zostrojte jeho CFG gramatiku, zdôvodnite, že daná gramatika popisuje jazyk LaTeX: L.
   b) [12b] Preveďte gramatiku na Chomského normální tvar (Definujte, čo je Choms. norm. tvar)

3) [21b] Je dána gramatika pravidly:

      S -> aSA | bB
      A -> aAb | b
      B -> aA

   a) [10b] Zostrojte zásobníkový automat
   b) [ 6b] Popište výpočet zásobníkového automatu z bodu a) přijímající slovo abababb.
   c) [ 5b] Ukažte, že slovo aabbba není přijímáno zásobníkovým automatem.

4) [24b] Daný je jazyk LaTeX:  L = \{1^{2k} 2^{3l+1} | k,l \ge 0\} 

   a) [12b] Dokažte, zda jazyk LaTeX: L^* je bezkontextový. (Definujte bezkontextový jazyk.)
   b) [12b] Dokažte, zda jazyk LaTeX: L^* je regulární. (Definujte regulární jazyk.)
Citováno z „http://oi.hanx.cz/wiki/index.php/JAG“
Events Upcoming
More »