[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

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? :)

MIKI wrote: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).

Ja bych jeste pridal otazku z druhe casti:

Udelat Turinguv stroj pro jazyk L={u | u=u^r} (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 -> a_iSa_i | a_i | 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!

ivan wrote:...Udelat Turinguv stroj pro jazyk L={u | u=u^r}
...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:

hippies wrote: Tak ono na TS simulovat zasobnik neni zase tak tezky ne? :wink:

!!!TAK UKAŽ!!!!

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?

Pre buduce generacie...

Q ={q₀, q₁,...,q_n, d₁,..., d_n, r₁,..., r_n, f }
X = {ε, x₁,...,x_n}
F = {f}

i,j=1,...,n

δ(q₀,ε) = (f,ε,0) prazdne slovo alebo prazna paska
δ(q₀,x_i) = (d_i,ε,+1) zapamataj si prve pismeno na paske a zmaz ho
δ(d_i,x_j) = (d_i,x_j,+1) chod na koniec pasky (dopredna fcia.)
δ(d_i,ε) = (r_i,ε,-1) ukaz na posledne pismeno
δ(r_i,x_i) = (z,ε,-1) odstran pismeno pokial suhlasi stym co mas zapamatane
δ(r_i,ε) = (f,ε,0) ak nemas co odstranit, potom pismeno bolo presne vstrede (slovo dlzky 2k+1)
δ(z,x_i) = (z,x_i,-1) vrat sa na zaciatok pasky (spatna fcia.)
δ(z,ε) = (q₀,ε,+1) ukaz na prve pismeno a pokracuj od zaciatku

alebo dvojhlavovy s jednou paskou (1. ani 2. hlava pasku nemeni)

δ(q₀,ε,ε) = (f,ε,0,ε,0)
δ(q₀,x_i,x_j) = (q₀,x_i,0,x_j,+1)
δ(q₀,x_i,ε) = (p,x_i,0,ε,-1)
δ(p,x_i,x_i) = (p,x_i,+1,x_i,-1)
δ(p,ε,ε) = (f,ε,0,ε,0)