Zkouška - 3.6.2013

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).
MadMan

Zkouška - 3.6.2013

Příspěvek od MadMan »

Kvíz klasika, na zákeřnosti co si vzpomínám

1) Máme slova u1..un, v1...vn, S je podmnožina {1..n}, a i1...in je nějaká permutace prvků z S, problém u_i1...u_in=v_i1..v_n je
a) algoritmicky nerozhodnutelný
b) algoritmicky rozhodnutelný
c) existuje Turingův stroj, který ten problém řeší
d) existuje Turingův stroj, který rozhoduje ten problém

správně b,c,d - jelikož v PKP se můžou prvky opakovat, tady máme konečný počet možností

2) Které regulární jazyky nad abecedou X nejdou více rozložit
a) prázdná množina
b) {\labda}
c) X
d) {x| x z X}

správně a,b ( d je to same jako b)

Víc si nevzpomínám na záludnosti a ústní : Sestrojit zásobníkový automat rozpoznávající prázdným zásobníkem {wcw^r | w z {a,b}*}, nejjednodušeji jednostavově, to mě napadlo později. Udělal jsem dvoustavový, ten bylo třeba převéct na bezkontextovou gramatiku a tu redukovat. Dále dokázat algoritmus redukce.

Hodně štěstí !
Návštěvník

Re: Zkouška - 3.6.2013

Příspěvek od Návštěvník »

oprava: u 2) d je to same jako c
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“