JAG

Z OI wiki

Přejít na: navigace, hledání

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) 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) Je dána gramatika LaTeX: G = (N, \Sigma, S, P), kde LaTeX: N = {S, A, B, C} ,  \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) 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) 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: 

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.)

a) [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 »