Surynek 26. 05. 2015

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
lkjasl

Surynek 26. 05. 2015

Příspěvek od lkjasl »

Na začátku byla jedna otázka na zařazení jazyka co nejpřesněji do chomského hierarchie (určitě bylo víc verzí, nejspíš měl každý svůj jazyk). Potom byl jeden důkaz z přednášky. Kolik na to bylo času to nevím, ale probíhalo to tak, že kdo měl zařazenej ten jazyk tak mu to šel ukázat a dostal druhou otázku.

Já dostal L = \{$kod(T)$ | L(T) = \varnothing$ nad abecedou $\{0,1\}\} a Kleeneho větu.
Katami
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 3. 2. 2014 13:40
Typ studia: Informatika Ph.D.

Re: Surynek 26. 05. 2015

Příspěvek od Katami »

Já jsem dostal L = \{ a^ib^jc^k | i = j = k \} a pumping lemma pro regulární jazyky.

Kolega dostal L = \{ a^p | p \text{ je prvo\v{c}\'{i}slo} \} a důkaz že lineárně omezené turingovy stroje přijímají právě kontextové jazyky.
Naposledy upravil(a) Katami dne 27. 5. 2015 07:43, celkem upraveno 1 x.
VImpaler
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 26. 5. 2015 14:18
Typ studia: Informatika Bc.

Re: Surynek 26. 05. 2015

Příspěvek od VImpaler »

L = \{ucv| u,v \in \{a,b\}^* \& u 
e v \} a definice rekurzivních jazyků, pokud existuje jazyk, který není rekurzivní a důkaz, že není rekurzivní. (třeba L_u)
Jenda_

Re: Surynek 26. 05. 2015

Příspěvek od Jenda_ »

Já dostal zařadit L_u a potom Myhill-Nerodovu větu. Nejspíš jsem tak sklidil ty jednodušší.
Jenda_

Re: Surynek 26. 05. 2015

Příspěvek od Jenda_ »

Koukám že nemám moc velký paměťový rozsah co do definice L_u :). Ne L_u (tj. kde by se vyžadovalo, že TS jím kódovaný musí slovo přijímat), ale jazyky kódující TS lhostejno zda přijmou. Takže stačilo udělat konečný automat, který zvalidoval, že to je ve formátu co jsme měli na přednášce.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“