[skúška] 10. 06. 08
[skúška] 10. 06. 08
Zdravím,
nasledujúci skúškový príklad som na tomto fóre nezaregistroval, so here goes:
Preveďte (nejakým obecne použiteľným algoritmom) nasledujúci regulárny výraz na (nedeterministický) konečný automat:
((ab + c)+a(bc)* + b)*
Rozumie sa, skonštruujte (nedeterministický) konečný automat, ktorý príjma jazyk reprezentovaný regulárnym výrazom.
Dokážte všetky tvrdenia, ktoré zaručujú, že tento prevod je možné urobiť vždy.
Hint:
1. Hodnotou regulárneho výrazu je regulárny jazyk. Uzavretosť triedy regulárnych jazykov na operácie zjednotenia, zreťazenia a iterácie.
2. Kleeneova veta (charakteristika regulárnych jazykov).
Pozorovanie:
Výsledok kvízu (po jeho úspešnom napísaní) má iba zanedbateľný vplyv na výslednú známku,
tj. i s 21 bodmi je možné uspieť výborne, rovnako ako s výšším počtom bodom pohorieť.
Cheerio
nasledujúci skúškový príklad som na tomto fóre nezaregistroval, so here goes:
Preveďte (nejakým obecne použiteľným algoritmom) nasledujúci regulárny výraz na (nedeterministický) konečný automat:
((ab + c)+a(bc)* + b)*
Rozumie sa, skonštruujte (nedeterministický) konečný automat, ktorý príjma jazyk reprezentovaný regulárnym výrazom.
Dokážte všetky tvrdenia, ktoré zaručujú, že tento prevod je možné urobiť vždy.
Hint:
1. Hodnotou regulárneho výrazu je regulárny jazyk. Uzavretosť triedy regulárnych jazykov na operácie zjednotenia, zreťazenia a iterácie.
2. Kleeneova veta (charakteristika regulárnych jazykov).
Pozorovanie:
Výsledok kvízu (po jeho úspešnom napísaní) má iba zanedbateľný vplyv na výslednú známku,
tj. i s 21 bodmi je možné uspieť výborne, rovnako ako s výšším počtom bodom pohorieť.
Cheerio
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: [skúška] 10. 06. 08
Mna by zaujimalo ako sa hodnoti, ked nedam dokazy niektorych popripade vsetkych dokazov 2. casti. Napriklad spravim dokaz cez umping lema, ze je nieco kontextove ale nedokazem priamo tu lemu. Ma stym niekto skusenosti?
// edit:
A nejake nove otazky z testiku by neboli?
// edit:
A nejake nove otazky z testiku by neboli?
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
Re: [skúška] 10. 06. 08
spravne hardcore otazka znie, co ked ani neviem naasociovat do nazvov/zneni viet, co som pouzil (nie, ze by sa to mohlo stat v spomenutom trivialnom pripade).MIKI píše:Mna by zaujimalo ako sa hodnoti, ked nedam dokazy niektorych popripade vsetkych dokazov 2. casti. Napriklad spravim dokaz cez umping lema, ze je nieco kontextove ale nedokazem priamo tu lemu. Ma stym niekto skusenosti?
Re: [skúška] 10. 06. 08
Ja bych jeste pridal otazku z druhe casti:
Udelat Turinguv stroj pro jazyk L={u | u=ur} (neboli u je palindrom), zaradit jazyk do Chomskeho chierarchie, a dokazat tvrzeni ktere nam pomohlo rozhodnout ze ho nejde zaradit do mensi tridy.
Kdyz jsem se kouknul na zadani, tak jsem se trosku zarazil, protoze jsem necekal TS v druhe casti. Nejak se mi nepovedlo ho sestavit, ale vsechno ostatni jsem mel, a pak jsem u ustni casti to ukecal, takze pohoda.
Jinak, ten jazyk je bezkontextovy (S -> aiSai | ai | e), a pres iteracni lemma se da dokazat ze neni regularni.
Pro zvedave, staci na google-u vyhledat "turing machine palindrome"
Preji hodne stesti u zkousek!
Udelat Turinguv stroj pro jazyk L={u | u=ur} (neboli u je palindrom), zaradit jazyk do Chomskeho chierarchie, a dokazat tvrzeni ktere nam pomohlo rozhodnout ze ho nejde zaradit do mensi tridy.
Kdyz jsem se kouknul na zadani, tak jsem se trosku zarazil, protoze jsem necekal TS v druhe casti. Nejak se mi nepovedlo ho sestavit, ale vsechno ostatni jsem mel, a pak jsem u ustni casti to ukecal, takze pohoda.
Jinak, ten jazyk je bezkontextovy (S -> aiSai | ai | e), a pres iteracni lemma se da dokazat ze neni regularni.
Pro zvedave, staci na google-u vyhledat "turing machine palindrome"
Preji hodne stesti u zkousek!
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: [skúška] 10. 06. 08
Tak ono na TS simulovat zasobnik neni zase tak tezky ne?ivan píše:...Udelat Turinguv stroj pro jazyk L={u | u=ur}
...Kdyz jsem se kouknul na zadani, tak jsem se trosku zarazil, protoze jsem necekal TS v druhe casti...
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Re: [skúška] 10. 06. 08
!!!TAK UKAŽ!!!!hippies píše: Tak ono na TS simulovat zasobnik neni zase tak tezky ne?
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: [skúška] 10. 06. 08
na zacatku si oznacis dno - na pasku si napises nejaky symbol..
nechas pracovat puvodni zasobnikovy automat, s tim, ze kdyz mas neco dat na zasobnik, tak posunes hlavu a zapises si to na pasku, kdyz to ze zasobniku ctes, tak to ctes tou hlavou a posunes ji zpet. Kdyz narazis na zarazku, mas prazdny zasobnik.
He?
nechas pracovat puvodni zasobnikovy automat, s tim, ze kdyz mas neco dat na zasobnik, tak posunes hlavu a zapises si to na pasku, kdyz to ze zasobniku ctes, tak to ctes tou hlavou a posunes ji zpet. Kdyz narazis na zarazku, mas prazdny zasobnik.
He?
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: [skúška] 10. 06. 08
Pre buduce generacie...
Q ={q0, q1,...,qn, d1,..., dn, r1,..., rn, f }
X = {ε, x1,...,xn}
F = {f}
i,j=1,...,n
δ(q0,ε) = (f,ε,0) prazdne slovo alebo prazna paska
δ(q0,xi) = (di,ε,+1) zapamataj si prve pismeno na paske a zmaz ho
δ(di,xj) = (di,xj,+1) chod na koniec pasky (dopredna fcia.)
δ(di,ε) = (ri,ε,-1) ukaz na posledne pismeno
δ(ri,xi) = (z,ε,-1) odstran pismeno pokial suhlasi stym co mas zapamatane
δ(ri,ε) = (f,ε,0) ak nemas co odstranit, potom pismeno bolo presne vstrede (slovo dlzky 2k+1)
δ(z,xi) = (z,xi,-1) vrat sa na zaciatok pasky (spatna fcia.)
δ(z,ε) = (q0,ε,+1) ukaz na prve pismeno a pokracuj od zaciatku
alebo dvojhlavovy s jednou paskou (1. ani 2. hlava pasku nemeni)
δ(q0,ε,ε) = (f,ε,0,ε,0)
δ(q0,xi,xj) = (q0,xi,0,xj,+1)
δ(q0,xi,ε) = (p,xi,0,ε,-1)
δ(p,xi,xi) = (p,xi,+1,xi,-1)
δ(p,ε,ε) = (f,ε,0,ε,0)
Q ={q0, q1,...,qn, d1,..., dn, r1,..., rn, f }
X = {ε, x1,...,xn}
F = {f}
i,j=1,...,n
δ(q0,ε) = (f,ε,0) prazdne slovo alebo prazna paska
δ(q0,xi) = (di,ε,+1) zapamataj si prve pismeno na paske a zmaz ho
δ(di,xj) = (di,xj,+1) chod na koniec pasky (dopredna fcia.)
δ(di,ε) = (ri,ε,-1) ukaz na posledne pismeno
δ(ri,xi) = (z,ε,-1) odstran pismeno pokial suhlasi stym co mas zapamatane
δ(ri,ε) = (f,ε,0) ak nemas co odstranit, potom pismeno bolo presne vstrede (slovo dlzky 2k+1)
δ(z,xi) = (z,xi,-1) vrat sa na zaciatok pasky (spatna fcia.)
δ(z,ε) = (q0,ε,+1) ukaz na prve pismeno a pokracuj od zaciatku
alebo dvojhlavovy s jednou paskou (1. ani 2. hlava pasku nemeni)
δ(q0,ε,ε) = (f,ε,0,ε,0)
δ(q0,xi,xj) = (q0,xi,0,xj,+1)
δ(q0,xi,ε) = (p,xi,0,ε,-1)
δ(p,xi,xi) = (p,xi,+1,xi,-1)
δ(p,ε,ε) = (f,ε,0,ε,0)
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.