Teoreticka informatika

[Casso]

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

[johnyo13]

tak, tak, cize p:{vsetky okrem ABKS}, {ABKS} - ekvivalentne budu AB a ABS

[johnyo13]

dost by sa hodil aj ten 1.priklad z druhej skupiny.. aspon nejaka istota 4 bodov!

[Hunterko]

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)

[Casso]

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)

[Hunterko]

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

[milaninho]

rozdiel je v tom ci uvazujes ZA s ukoncenim finalovym stavom(to je tento pripad) alebo vyprazdnenim zasobnika(to by bol pripad keby si to Z odobral, potom by si nepotreboval finalovy stav).. aspon taky je moj nazor

[Casso]

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.

[buhehe]

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

kedy viem ze sa zobrazenie da zrealizovat automatom?

[kOsTi]

musi tam splnat podmienky rozne... sekvencnost, zachovanie dlzky atd... urcit bazu... sa to robilo na cviku

[les paul]

moja skupina mala 

1.priklad:

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

ostatne uz bolo napisane

enjoy

[milaninho]

kedy viem ze sa zobrazenie da zrealizovat automatom?

musi splnat 4 podmienky:
1. musi to byt sekvencne zobrazenie
2. musi to byt zobrazenie so zachovanim dlzky
3. musi byt konecnej vahy
4. musi byt bez predikcie

viac vid prednasky..

[Casso]

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

[trek]

jj tak nejak aj mne vyslo na pisomke ...malo sa ti zredukovat na 3 stavy urcite

[valentino]

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

no mne zase uplne inac

Q   |0   |1
-----------
S   |SK  |A
SK |SK  |A
A   |SB  |-
SB |SK  |A

[Casso]

ale S a SB sa daju spojit nie?

[valentino]

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

[dalcasian]

vsetky tri nie lebo to ani nesedi, ked si nakreslis automat. Potom asi treba spravit stavy P1, P2..az pokial nie je zhoda. Mne vzniklo nieco take...
Cize prve delenie je podla toho, kde je koncovy stav...a do druhej mnoziny dame vsetko co nam ostalo

P1: {S, A, SB} {SK}
P2 sa mne rovna P1 !? 

[Casso]

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

[valentino]

oki, takze koncovy musime oddelit ako prvy, dobre tak potom to sedi, dakujem.

[dalcasian]

oki, takze koncovy musime oddelit ako prvy, dobre tak potom to sedi, dakujem.

a teraz ked to oddelime, tak ako to bude lebo akosi som sa zamotal jak cap do lanca 

[Payne]

Takze nakoniec to tak vyjde ze ekvivalentne stavy budu S a SB, co inak sa da aj z obrazku celkom prist na to...

Inak ja som vobec nevedel ani korecko nic nevravel ze uz rovno pri determinizacie daktore stavy mozem davat prec. Kazdopadne aj ked ich nedam tak potom pri redukcii stavov idu prec, cize je to jedno vlastne...

[Casso]

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

[kOsTi]

cela vstupna abeceda je [ a ]

je to len
(q0,[,Z,q1,[Z)
(q1,[,[,q1,[[)
(q1,],[,q1,lambda)
(q1,lambda,Z,q0,Z)

podla toho co vravel Korecko tak ma ma vediet rozpoznavat len take daco [[[]]][][[]] atd

[Hunterko]

cela vstupna abeceda je [ a ]

je to len
(q0,[,Z,q1,[Z)
(q1,[,[,q1,[[)
(q1,],[,q1,lambda)
(q1,lambda,Z,q0,Z)

podla toho co vravel Korecko tak ma ma vediet rozpoznavat len take daco [[[]]][][[]] atd

jj tiez sa mi take nieco mari... ale tento tvoj nikdy neskonci to neviem ci je dobre posledny prikaz bud by som dal do qF alebo miesto Z lambdu...