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

Google drive

Řešené příklady stylem prezentací, velmi šikovné: http://www.cs.vsb.cz/kot/animace.php

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

Online DFA Simulator - https://jakubbegera.github.io/DFASimulator/

Vynikající JAVA prográmek k simulaci FSM, RE, gramatik [Doporučuji]

  • redukce automatu
  • NFA -> DFA
  • bezkontextová gramatika -> zásobníkový automat
  • RE <-> automat <-> gramatika
  • pumping lemma
  • Téměř vše lze krokovat :)
  • Ke stažení: http://oi.hanx.cz/files/JAG/JFLAP.jar

Ukázkové testy

ukázka1 (PDF)
ukázka2 (PDF)

Zkoušky akademický rok 2016/2017

17.1.2017
31.1.2017
7.2.2017
14.2.2017 část 1 část 2 část 3


Zkoušky akademický rok 2014/2015

8.1.2015
14.1.2015

Zkoušky akademický rok 2012/2013

15.1.2013 9:00

--Kejvaja1 2. 2. 2013, 19:26 (UTC)

nechtělo se mi to nijak upravovat ;)

zadání (foto, JPEG);

Zkoušky akademický rok 2011/2012

23.1.2012 9

http://oi.hanx.cz/files/JAG/Zkouska%2023-01-2012.jpg

3.1.2012 9:44

Napsal jsem, co si pamatuji, kdyžtak doplňte --Dobriric 3.1.2011, 13:00 (UTC) 

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

   LaTeX: 
   \textbf{
   \begin{tabular}{|r|r|r|}
   \hline 
     & a & b \\
   \hline
   $\rightarrow$ 1 & 2 & 4 \\
   \hline
   2 & 3 & 4 \\
   \hline
   $\leftarrow$ 3 & 4 & 3 \\
   \hline
   4 & 4 & 4 \\
   \hline
   \end{tabular}}
   
   
   a) [?b] Sestrojte konečný DFA LaTeX: M_1 pro LaTeX: L_1, zdůvodněte fakt, že jazyk přijímá.
   b) [?b] Automat LaTeX: M_1 zredukujte, nebo ukažte, že je již zredukovaný.   
      ad a)b):obrazek na OI wiki
   c) [4b] Určete, zda platí některá z inkluzí LaTeX: L_1\subseteq L_2,\,L_1\subseteq L_2. Své tvrzení zdůvodněte, v případě neplatnosti nalezte protipříklad.
   d) [?b] Napište regulární výraz pro LaTeX: L_1\cup L_2

2) [?b] Je dána bezkontextová gramatika LaTeX: G = (N, \Sigma, S, P), kde LaTeX: N = \{S, A, B, C\}    LaTeX:  \Sigma = \{a, b\} a pravidly P: 
   
   ----pravidla nedám dohromady----
   
   a) [?b] Ke gramatice LaTeX: G najděte gramatiku LaTeX: G_1 v Chomském normálním tvaru. Generuje gramatika LaTeX: G_1 stejný jazyk, jako LaTeX: G. 
   b) [?b] Najděte levou derivaci slova LaTeX: bbaaab v gramatice LaTeX: G_1 a nakreslete pro ni derivační strom.
   c) [?b] Najděte slovo LaTeX: u=\{a, b\}^* délky alespoň 5, které není generováno gramatikou LaTeX: G (ani LaTeX: G_1), zdůvodněte.
   d) [2b] Je gramatika LaTeX: G víceznačná? Pojem víceznačnosti definujte.

3) [?b] Jsou dány dva jazyky LaTeX: L_1 a LaTeX: L_2 nad abecedou LaTeX:  \Sigma = \{a, b\}, LaTeX:  L_1 = \{a^m b^{2n}  |  m,n \geq 0\}  a LaTeX:  L_2 = \{a^i b^i a^j  |  i,j \geq 0\} 
   
   a) [ ?b] Sestrojte konečný automat LaTeX: M_1, který přijímá jazyk LaTeX: L_1.
   b) [ ?b] Sestrojte zásobníkový automat LaTeX: M_2, který přijímá jazyk LaTeX: L_2.
   c) [ ?b] Sestrojte zásobníkový automat LaTeX: M, který přijímá průnik jazyků LaTeX: L=L_1\cap L_2.
   d) [?b] Na zásobníkovém automatu LaTeX: M ukažte zpracování slova LaTeX: aabbaa.

4) [22b] Je dán jazyk LaTeX:  L = \{0^{i+2} (12)^i |  i \geq 0 \}  nad abecedou LaTeX:  \Sigma = \{0, 1, 2\}.
   
   a) [11b] Rozhodněte, zda je jazyk LaTeX: L bezkontextový. Definujte, co to je bezkontextový jazyk.
   b) [11b] Rozhodněte, zda je jazyk LaTeX: L regulární. Definujte, co to je regulární jazyk.

Zkoušky akademický rok 2010/2011

4.2.2011 10:00

zadání (foto, JPEG);

28.1.2011 10:00

zadání (foto, JPEG);

přepis zadání --Hanx 2. 2. 2011, 18:15 (UTC) 

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

   LaTeX: 
   \textbf{
   \begin{tabular}{|r|r|r|r|}
   \hline 
     & a & b & c \\
   \hline
   $\rightarrow$ 1 & 7 & 3 & 3 \\
   \hline
   2 & 7 & 1 & 7 \\
   \hline
   3 & 4 & 2 & 7 \\
   \hline
   $\leftarrow$ 4 & 7 & 6 & 6 \\
   \hline
   5 & 7 & 4 & 7 \\
   \hline
   6 & 1 & 5 & 7 \\
   \hline
   7 & 7 & 7 & 7 \\
   \hline
   \end{tabular}
   }
   
  
   a) [10b] Sestrojte konečný DFA LaTeX: M_1 pro LaTeX: L_1, zdůvodněte fakt, že jazyk přijímá.
   b) [ 5b] Napište regulární výraz odpovídající jazyku LaTeX: L_2.
   c) [10b] Sestrojte konečný DFA LaTeX: M přijímající průnik  jazyků LaTeX: L=L_1\cap L_2.
   d) [ 5b] Výsledný automat LaTeX: M redukujte.

  --------------------------------------------------------------------------------------------------------------------------------------------

  Ad c) Vie niekto, ako to vyriešiť? Prehľadal som už všetky možné zdroje a nemôžem nájsť žiaden algoritmus alebo návod ako daný prienik získať.
        Vďaka --Noskoja1 31. 1. 2011, 20:01 (UTC)

     -> zkus se podívat sem, strana 52 - na průnik používá stromvý algoritmus (str. 49). Snad to pomůže ;) --Hanx 31. 1. 2011, 22:26 (UTC)

     -> mas dve DFA pro dva jazyky, sloucis jejich vstupni stavy, na zaklade toho vyrobis novy DFA, pokud chces prunik, tak vystupni stavy
        jsou ty, kde se slouci vystupni stav 1. a 2. DFA (pokud sjednoceni, tak staci aby to byl bud vystupni 1. nebo 2. DFA, pokud rozdil
        jazyku, tak jsou vystupni stavy jen ty, kde se slucuje vystupni stav prvniho, se stavem, ktery neni vystupni v druhem) 
        --Adamema4 1. 2. 2011, 10:38 (UTC)


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

     S -> BAC|AC
     A -> BA|LaTeX: \varepsilon
     B -> BB|b
     C -> BC|a
   
   a) [10b] Ke gramatice LaTeX: G najděte gramatiku LaTeX: G_1 v Chomském normálním tvaru, která keneruje stejný jazyk jako LaTeX: G.
   b) [ 8b] Najděte levou derivaci slova 'bbbba' v každé z gramatik LaTeX: G a LaTeX: G_1.
   c) [ 6b] Najděte slovo LaTeX: u=\{a, b\}^* délky alespoň 5, které není generováno gramatikou LaTeX: G, zdůvodněte.

  --------------------------------------------------------------------------------------------------------------------------------------------

      \\Jak presne urcim zda je jazyk bezkontextovy ci nikoli to same pro regularni jazyk...pripadne nejake materialy predem diky
      
      Zeby Pumping lemma nebo Nerodova veta pro pripad regularniho jazyku?Pokud mas na mysli postup, tak to zalezi na konkretnim jazyku.

3) [22b] Jsou dány dva jazyky LaTeX: L_1 a LaTeX: L_2 nad abecedou LaTeX:  \Sigma = \{a, b\}, LaTeX:  L_1 = \{a^{2k + 1} b^{3l}  |  k,l > 0\}  a LaTeX:  L_2 = \{a^i b^j  |  0 \leq i<j\} 
   
   a) [ 8b] Sestrojte bezkontextovou gramatiku LaTeX: G_1, která generuje jazyk LaTeX: L_1.
   b) [ 8b] Sestrojte bezkontextovou gramatiku LaTeX: G_2, která generuje jazyk LaTeX: L_2
   c) [ 6b] Sestrojte bezkontextovou gramatiku LaTeX: G, která generuje jazyk LaTeX: L=L_1L_2

4) [24b] Je dán jazyk LaTeX:  L = \{(01)^i 1^{2i} |  i \geq 0 \}  nad abecedou LaTeX:  \Sigma = \{0, 1\}.
   
   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.

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: 
   \textbf{
   \begin{tabular}{|r|r|r|}
   \hline 
     & a & b \\
   \hline
   $\rightarrow$ 1 & 2 & 4 \\
   \hline
   2 & 3 & 4 \\
   \hline
   $\leftarrow$ 3 & 4 & 3 \\
   \hline
   4 & 4 & 4 \\
   \hline
   \end{tabular}
   }
   
  
   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 »