JAG

Z OI wiki

Verze z 31. 1. 2011, 22:26

Info o předmětu

• A4B01JAG - Jazyky,automaty a gramatiky

• Přednášející: prof. RNDr. Marie Demlová, CSc.

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

Pravidla předmětu

Stránka předmětu

Studijní materiály

Ř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

Zkoušky

28.1.2011 10:00

zadání (foto, JPEG)

Pomoc s riešením príkladu:

1.c) Sestrojte deterministický konečný automat přijímajíci průnik jazyků.

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)

14.1.2011 10:00

1) [30b] Je dán jazyk : 
   a jazyk :

   
  
   a) [10b] Sestrojte DFA  pro, zdůvodněte, proč jazyk přijímá.
   b) [ 4b] Napište regulární výraz pro jazyk .
   c) [ 8b] Rozhodněte, zda platí , zdůvodněte nebo uveďte protipříklad.
   d) [ 8b] Rozhodněte, zda platí , zdůvodněte nebo uveďte protipříklad.

2) [20b] Je dána gramatika , kde     a pravidly P: 

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

3) [24b] Je dán jazyk 
   
   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ě .
   c) [ 7b] k zásobníkovému automatu z a) zkonstruujte zásobníkový automat,
            který přijímá jazyk  prázdným zásobníkem.

4) [24b] Je dán jazyk 
   
   a) [12b] Rozhodněte, zda je jazyk  bezkontextový. Definujte, co to je bezkontextový jazyk.
   b) [12b] Rozhodněte, zda je jazyk  regulární. Definujte, co to je regulární jazyk.

7.1.2011 10:00

1) [30b] Dva regulárne výrazy:
  
       
   
   a) [10b] Zostrojte DFA  pre reg. výraz  (jazyk ) a DFA  pre reg. výraz  (jazyk ).
   b) [10b] Zostrojte DFA  pre rozdiel jazykov 
   c) [ 5b] Automat  redukujte
   d) [ 5b] Napíšte regulárny výraz odpovedajúci automatu 

2) [25b] Daný je jazyk 

   a) [13b] Zostrojte jeho CFG gramatiku, zdôvodnite, že daná gramatika popisuje jazyk .
   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 

   a) [12b] Dokažte, zda jazyk  je bezkontextový. (Definujte bezkontextový jazyk.)
   b) [12b] Dokažte, zda jazyk  je regulární. (Definujte regulární jazyk.)