[skúška] 10. 06. 08

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

[skúška] 10. 06. 08

Příspěvek od amanwithnoname »

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
MIKI
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

Příspěvek od MIKI »

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? :)
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ť.
univerz2

Re: [skúška] 10. 06. 08

Příspěvek od univerz2 »

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? :)
spravne hardcore otazka znie, co ked ani neviem naasociovat do nazvov/zneni viet, co som pouzil :D (nie, ze by sa to mohlo stat v spomenutom trivialnom pripade).
ivan
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 15. 6. 2007 00:32

Re: [skúška] 10. 06. 08

Příspěvek od ivan »

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!
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: [skúška] 10. 06. 08

Příspěvek od hippies »

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...
Tak ono na TS simulovat zasobnik neni zase tak tezky ne? :wink:
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ů..
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: [skúška] 10. 06. 08

Příspěvek od lickra »

hippies píše: Tak ono na TS simulovat zasobnik neni zase tak tezky ne? :wink:
!!!TAK UKAŽ!!!!
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: [skúška] 10. 06. 08

Příspěvek od hippies »

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?
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ů..
MIKI
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

Příspěvek od MIKI »

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)
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ť.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“