Messages

..

tak toto si uplne zle pochopil..

jj prekomplikoval som to, sry 

B3 skupina utorok 7:30
http://img227.imageshack.us/img227/5876/01122009.jpg

(sry za kvalitu, lepsie ako dratom do oka )

idem spat, rano 7:30 ma to caka

McLarenPP spominal aj nasobenie (krat)

2.priklad - zasobnikovy automat pre jazyk zatvorkovych vyrazov (hranate zatvorky, medzi zatv. vyrazy patria aj alfa, beta, alfa krat beta - take daco)

Pokus o riesenie:
vstupna abeceda: {a,b,+,*,[,]}
abeceda zasobnika: {V,Z,[,O}

Program:
(q0,a,Z,qo,VZ) - Nacitanie prveho symbola do zasobnika
(q0,b,Z,qo,VZ) -  -||-
(q0,[,Z,qo,[Z)  -  -||-
(q0,a,[,q0,V[) -  Nacitanie symbolu za zatvorkou do zasobnika
(q0,b,[,q0,V[) -   -||-
(q0,[,[,q0,[[) -    -||-
(q0,*,V,q0,O) -  Vyraz* - ocakava hruhy operand
(q0,+,V,q0,O) -  vyraz +
(q0,a,O,q0,V) -  vyraz operator vyraz >> vyraz
(q0,b,O,q0,V) -   -||-
(q0,[,O,q0,[O) -   vyraz operator [vyraz]
(q0,],V[,q0,V)  -  [vyraz] >> vyraz
(q0,],V[O,q0,V)  -  vyraz operator [vyraz] >> vyraz
(q0,lambda,VZ,qF,Z) - ak cely retazec je jeden vyraz >> finalny stav

Co vy na to? zabudol som na nieco?
(EDIT: uz som nasiel podobny priklad v zbierke a tam to uplne inak riesia kua:-()

ale S a SB sa daju spojit nie?

tak potom ale nemozes spojit vsetky 3?
Q   |0   |1
-----------
S   |SK  |A
SK |SK  |A
A   |SB  |-
SB |SK  |A

K by sa rovnalo S+SK+SB...

to zas nie, lebo SK je koncovy stav a S a SB su nekoncove

takze, test naklikany, vsetko bolo podla nasich ocakavani...

gl 

mas na mysli ocakavania typu test2.1-2.4  alebo ten textak? 

ale S a SB sa daju spojit nie?

Najdite KSA jazykovo ekvivalentny s reg. gramatikou G ... determinizovať a redukovať
G:
S -> 0S | 1A | 0
A -> 0S | 0B
B -> 0

mate niekto toto vyriesene?
vyslo mi nieco take (typos bingo):

Q|0|1
------
A|S|-
S|K|A
K|K|A

[bud]

to aky je rozdiel ci zmazes ten Z znak alebo ho tam nechas ? ale diky kazdopadne

Slovo sa akceptuje bud vyprazdnenim zasobnika alebo prechodom do finalneho stavu.

[Z]

ten zasobnikovy automat je taky lahky ci som to zle pochopil ?
je tam ze a^n b^2n | n>=1

takze by to mohlo byt takto?

(q0,a,Z,q0,aaZ)
(q0,a,a,q0,aaa)
(q0,b,a,q1,lambda)
(q1,b,a,q1,lambda)
(q1,lambda,Z,qF,lambda)

mas to dobre ale poslednu instrukciu by som napisal radsej takto:
(q1,lambda,Z,qF,Z)

vsak ale tam sa triedy ekvivalencie nedaju urcit, ked nevieme vystupy. Nie? A ked nevieme spravit triedy ekvivalencii, tak nevieme spravit redukciu. Ci kde je chyba v mojich uvahach?

ak nevieme vystupy tak sa delia stavy do dvoch tried: koncove a nekoncove

mozes nakreslit a potom to niekam zavesit? diq

Netvrdim ze je to dobre ale ak by som to dostal na pisomke, nakreslil by som tam toto:

[3.priklad]

3.priklad

Zistite ci sa zobrazenie FI da realizovat konecnym automatom,
FI: {0,1,2}* -> {0,1}*
y(i)= 1 ak N2(x(i))mod2=0
y(i)= 0 inak

To vase zadanie bolo lahsie by som povedal, ale ten treti priklad neviem nejako - nevidim to ani v zosite. Nemoze to tu niekto vyriesit?
Pripadne ak ma niekto cas, tak aj ten turing z druheho zadania...

vyznam by mi to davalo jedine ak by tam bolo ze:
y(i)= 1 ak N2(x)mod2=0
v tom pripade je na vystupe jednotka ak je pocet symbolov 2 vo vstupnom slove X delitelny dvoma

EDIT: to x(i) znamena asi retazec po i-tý znak
EDIT2: riesenie je jednoduche, dva stavy: P/1 N/0, pociatocny stav je P, a pri vstupe 0 alebo 1 sa ostava v stave, pri dvojke sa prechadza z jedneho do druheho
EDIT3: na poziadanie aj obrazok nakreslim:-DD

obcas sa ten znak pouziva ako "alebo" takze to moze obcas zmiest

otazka:
mam upravit mealy automat na moorov. v mealy automate mam pociatocny stav A, v moorovom mi vznikne A/0 a A/1. Ktory z nich je pociatocny? ak zvolim oba, tak mi vznikne nedeterministicky automat, nie?

portal

aky?:-DDD

sak tam je {a,b}*, * znamena 0 a viac krat

sak pisem ze v zadani taka podmienka nieje... niekto to prekombinoval a zabudol uviest cele znenie zadania, klasika v tych knihach...

Chcem sa spytat ze v tej plocicovej zbierke priklad 4.6 to je dobre ratany? dajak mi tam naviac prida ten stav q1. Dalej stat 4.2 to dakto ratal na cvikach? bo my ani nie...

bez dvoch stavov by ti presiel aj prazdny retazec (hoc v zadani taka podmienka nieje....)

no pockaj v tomto pripade sa automat zastavi prechodom do koncoveho stavu qF pretoze este vzdy je v zasobniku Z, ak by posledna instrukcia bola (q1, lambda, Z, q1, lambda) potom by sa automat zastavil vyprazdnenim zasobnika nie?

Presne. v zbierke su uvadzane tusim obe metody zastavenia. Obcas mam pocit ze to tak robia aby nas viac zmiatli...

diky moc... tak uz asi chapem.. cize tam sa neriesia take veci ze napr. ked citame uz tie jednotky: na vstupe bude dalsia jednotka ale zasobnik bude uz prazdny...

Po vyprazdneni zasobnika , t.j. Odstranenia dna Z, sa automat zastavi.

ah kua nejak som zabudol o co ide v tych zasobnikovych automatoch :/ vedel by to niekto troska vysvetlit na tom priklade?

   L = {0ⁿ1ⁿ | n > 0}

thx

Trocha "teorie" na uvod:
format instrukcii hadam ovladas ale pre istotu: (aktualny stav, vstup,vrchol zasobnika, nasledujuci stav, novy vrchol zasobnika)
Z - symbol oznacujuci dno zasobnika
Po kazdej instrukcii sa posunie citacia hlava o jeden krok doprava

takze program:
(q0, 0, Z, q0, 0Z), pri nacitani prvej nuly za vyberie Z zo zasobnika a nahradi dvojicou 0Z (vpodstate ako keby si dal 0 na vrch)
(q0, 0, 0, q0, 00) pri dalsich nulach sa jednoducho da navrch dalsia nula (jedna sa akokeby vyberie a daju sa tam dve)
(q0, 1, 0, q1, lambda) prva jednotka; zo zasobnika sa vyberie nula ( vyberie sa nula a do zasobnika sa vopcha "nič")
(q1, 1, 0, q1, lambda) to iste ako predchadzajuca instrukcia, ale pre ostatne jednotky
(q1, lambda, Z, qF, Z) ak boli nacitane vsetky znaky (vstup je lambda) a v zasobniku nieje ziadna nula (len dno) to znamena ze pocet nul a jednotiek bol rovnaky. v tomto pripade sa prejde do finalneho stavu

dufam ze som to napisal dobre, predsa je uz 10hodin. tazko sa to vysvetluje takto nadialku...

Hej a take tie regularne vyrazy a take cudne obrazky hned po tom, to nikto nespominal ze by mohlo byt, co? lebo su to celkom dost bludy

my sme to mali na cviku a je to pomerne jednoduche, teda ak myslis to ze ako sa riesi sekvencia, rekurzia, vetvenie a pod v regularnych vyrazoch. Ku kazdemu prvku r.v. tam je nejaky k.s.a, ktoreho pospajanim ti vznikne k.s.a. rozoznavajuci cely regularny vyraz.  ten sa da este zvycajne zredukovat

potom pre priklad 4.1 nestaci takto?

Code [Select] Expand

(q0, 0,Z, q0, 0Z)
(q0, 0, 0, q0, 00)
(q0, 1, 0, q0, lambda)
nebude slovo akceptovane vyprazdnenim zasobnika?

podlamna je to jedna z variant. Myslim ze by ti to cviciaci uznal, a ak nie tak by si sa dohadal k pravde

aj prazdne slovo je riesenie..

väcsinou sme davali, ze (q0, lamb, Z, qf, lamb); kde qf je finalovy stav

Uz som si to dostudoval, Akceptovanie moze byt realizovane dvojako:
1. vyprazdnenim zasobnika (nahradenim symbolu Z symbolom "lambda")
2. Prechodom do finalneho stavu (Zvycajne q_f)