PRŮBĚH PŘEDNÁŠKY FORMÁLNÍ JAZYKY A AUTOMATY (LETNÍ SEMESTR 2009/2010)

===========================  3.3.2010  ===========================

Symbol, slovo, prázdné slovo, délka slova, jazyk, zřetězení slov a jazyků, iterace.
Jazyky s konečnou reprezentací.
Reprezentace jazyka pomocí generování a přijímání nedeterministickým algoritmem.
Zmínka o třídách P, NP a problému P ?= NP.
Příklad generování a přijímání množiny symetrických slov pomocí zásobníku.
Příklad generování jazyka a^nb^n pomocí pravidel
  S -> ABS, BA -> AB, BS -> b, Aa -> aa, Ab -> ab, Bb -> bb.
Cvičení: Dokažte, že všechna vygenerovaná slova obsahují nejprve neterminály (velká
písmena) a pak terminály (malá písmena).

===========================  10.3.2010  ===========================

Dokončeno cvičení na sestavení gramatiky pro jazyky a^ib^i a a^ib^ic^i.
Princip sestrojení gramatiky generující libovolný jazyk, který lze rozpoznávat Turingovým strojem.
Gramatiky typu 0,1,2,3 v Chomského hierarchii.

===========================  17.3.2010  ===========================

Zavedení pojmů přechodový diagram, konečný automat, regulární výraz.
Souvislost přechodových diagramů a gramatik typu 3.
Příklad konečného automatu s výstupem pro rozlišování typů čísel ve zdrojovém kódu programu.

Dále bude výuka probíhat v konzultačním režimu.

Cvičení.

Nalezněte KA a RV pro jazyky
  L_{1,1} = |w|_a sudé
  L_{1,2} = |w|_b sudé
  L_1 = průnik L_{1,2} a L_{1,1}
  L_2 = sjednocení L_{1,2} a L_{1,1}
  L_3 = |w|_b - |w|_a dělitelný 3

Nalezněte
  PD a KA pro slova obsahující "aba".
  pomocí komplementu pak KA pro slova neobsahující "aba".
  PD a KA pro slova obsahující "ababc".

Dokažte rovnost jazyků
  (b + eps)(a + ab)^*, (a + ba)^*(b + eps)

Nalezněte co nejmenší KA pro jazyk slov tvaru w = x_1 x_2 ... x_n v abecedě {a,b}, která splňují
  podmínku x_{n-k} = a. Dokažte, že je minimální pomocí ekvivalence slov podle jazyka.

Nalezněte KA M_k pro čísla v desítkové soustavě dělitelná k pro k = 3, 11, 7.