==================  30.9.2003  ===================

Motivace pro matematické studium jazyků:
 - analýza přirozeného jazyka
 - metamatematika, logika
 - počítače, programování

Pojmy: symbol, abeceda, slovo, jazyk, prázdné slovo, zřetězení, délka slova.
Konečná reprezentace, existence jazyků bez konečné reprezentace.

Příklady reprezentace:
 - jednoduchý generativní systém (správná uzavorkování)
 - konečný automat pro rozpoznávání typu čísel v zápisu programu

==================  7.10.2003  ===================

Příklady konečných automatů:
 - dokončení příkladu rozliąování čísel v programu
 - kámen na ąachovnici 2x2 (abeceda n,d,l,p)
 - ąipka na ąachovnici 2x2 (abeceda k,l,p)
 - dělitelitelnost čísel 3 a 7
Exaktní definice konečného automatu, roząířená přechodová funkce, jazyk
 rozpoznávaný automatem.
Daląí operace s jazyky, zřetězení, mocniny jazyka.
Cvičení na příątě: rovnice L=LX, asociativita zřetězení.

==================  14.10.2003  ==================

Dokončení cvičení:
 - řeąení rovnice L=LX
 - důkaz asociativity zřetězení jazyků
Definice regulárních jazyků a výrazů.
Cvičení. Navrhněte KA a RV pro jazyky:
 - slova neobsahující bb (KA)
 - slova délky dělitelné 2 nebo dělitelné 3 (RV,KA)
 - slova w splňující, ľe |w|_a je děl 2 a |w|_b není dělitelné 2 (KA, příątě RV)
 - slova obsahující ababc (RV, doma KA)

==================  21.10.2003  ==================

Příklady:
 - KA pro jazyk obsahující slovo ababc (zbývá otázka optimality)
 - RV pro jazyk slov se sudým |w|_a a lichým |w|_b (nedokončeno)

Zavedení přechodových diagramů, w-cesta, jazyk L(D) definovaný přechodovým
diagramem D.

==================  4.11.2003  ===================

Dořeąení optimality KA pro jazyk (a+b+c)*ababc(a+b+c)*.
Dokončení RV pro |w|_a sudé, |w|_b liché.
Připomenutí definice PD.
Příklad a*b*c*d*... na zjednoduąení PD pomocí eps-přechodů.
Plánované transformace: PD <-> KA, PD <-> RV.
Definice ekvivalence reprezentací.
Věta: Ke kaľdému RV existuje ekvivalentní PD.
  iterace ponechána jako cvičení

==================  11.11.2003  ==================

Důkaz konstrukce pro iteraci jazyka určeného přechodovým diagramem.
Zmínka o tom, ľe struktura RV odpovídá strukturovaným programům psaným
  pomocí if-then-else, repeat-until, while-do, begin-end
  (také sériově-paralelním grafům),
  zatímco PD odpovídají programům s libovolným pouľíváním příkazu goto
  (tj. obecným grafům)
  Transformace PD na RV musí tento rozdíl překonat => musí se pouľít trik.
Kleeneova věta: Ke kaľdému PD existuje ekvivalentní RV.

==================  18.11.2003  ==================

Ke kaľdému KA existuje ekvivalentní PD (stačí KA namalovat jako diagram).
Ke kaľdému PD existuje ekvivalentní KA (podmnoľinová konstrukce).
Daląí operace s KA (průnik, sjednocení, rozdíl, symetrický rozdíl).

==================  25.11.2003  ==================

Cvičení:
L_1 = jazyk slov obsahujících identifikátor i před identifikátorem t.
L_2 = jazyk slov neobsahujících identifikátor i.
L je sjednocení L_1 a L_2
Pouľijeme značení:
  a = písmeno kromě i,t nebo číslice
  n = znak, který není ani písmeno ani číslice
  i = písmeno i
  t = písmeno t
udělat PD pro L_i
převést je na KA podmnoľinovou konstrukcí
vytvořit součinový automat pro sjednocení

==================   2.12.2003  ==================

Přednáąka odpadla.