Teoreticka informatika

[puq]

napis mu to jazykom ZA potom mozno pochopi

[BossZ]

portal

zeby: https://student.tuke.sk/portal/home.mais

q0, student,Z, q0, studentZ
q0, .tuke, student, q0,student.tuke
q0, .sk/portal, .tuke, q1, .tuke.sk/portal
q1, lambda, .sk/portal, qf, .sk/portal
//vysledne slovo: student.tuke.sk/portal



//prepac, nedalo mi neopravit to..

[Casso]

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?

[McLarenPP]

co mam info od spoluziaka :
boli 2 skupiny, obidve mali 2 rovnake typy prikladov -
1.priklad - boli zadane pravidla gramatiky a bolo treba z nich spravit KSA, potom determinizovat a redukovat.
2.priklad - zasobnikovy automat pre jazyk zatvorkovych vyrazov (hranate zatvorky, medzi zatv. vyrazy patria aj alfa, beta, alfa krat beta - take daco)
a 3.priklad bol iny v kazdej skupine - jedna mala Turingov stroj, co som rozumel tak pre L = { x c | x patri {0,1}* , N(0) = N(1) }, druha skupina mala nejake sekvencne zobrazenie

vsetko za 4b, a este ze ti, co pojdu dnes, dostanu rovnake priklady (neviem ci len u Kozurka alebo aj u Lalovej), a ze zajtra maju byt priklady pozmenene.

[zerg1986]

Zapoctovka:

1.priklad:

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

2. priklad

Dokazte ze jazyk L je deterministicky a bezkontextovy,
L={a^n b^2n |n>=1}
PS: potrebne zostrojit zasobnikovy automat

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

Uz mam za sebou 

[Killian]

a 3.priklad bol iny v kazdej skupine - jedna mala Turingov stroj, co som rozumel tak pre L = { x c | x patri {0,1}* , N(0) = N(1) }, druha skupina mala nejake sekvencne zobrazenie

Prosim vysvetlite mi ako vyzera ten jazyk  L = { x c | x patri {0,1}* , N(0) = N(1) }, co je to  x c | x ?? Nejake vzorove slova moze niekto napisat?

[puq]

mas slovo ktore konci c aspon tak si to vysvetlujem ze napriklad: 100011011c a mas zistit ci sa rovna pocet 0 a 1

[McLarenPP]

to "|" je len oddelovac, jazyk ma byt "x c", za oddelovacom su podmienky. x ma patrit {0,1}* a zaroven N0(x) = N1(x)

[Casso]

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

[Killian]

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

[Casso]

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

[zerg1986]

EDIT: to x(i) znamena asi retazec po i-tý znak

Presne tak

[Killian]

Do certa, sekvencne zobrazenie dali?  To nechapem vobec, tusim este aj Lalova vravel ze to asi nebude lebo sa to tazko opravuje....
Nema niekto to zadanie co bolo s tym sekvencnym? Idealne aj riesenie?

[dalcasian]

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

mozes nakreslit a potom to niekam zavesit? diq

[johnyo13]

prvy priklad mi vychadza daco take:
Q/S     0     1
S       S     A
A       A     AB
AB      AB   ABKS
ABKS  ABS  ABKS
ABS    ABS  ABKS

je to dobre? bo som to fest rychlo robil, tak je velka sanca ze som sa niekde pomylil...

[buhehe]

este ti chybaju prechody pre stav ABS, mne vznikli 2 ekv. stavy (AB,ABS)

[johnyo13]

aha, kurna som si myslel, ze som v tej rychlosti daco zabudol
A este k druhemu prikladu, ked spravim automat, jak dokazem tie veci?

[buhehe]

no ze jazyk je deterministicky a bezkontextovy dokazes tym ze si zostrojil deterministicky zasobnikovy automat...teda dufam

[Casso]

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:

[Killian]

este ti chybaju prechody pre stav ABS, mne vznikli 2 ekv. stavy (AB,ABS)

Napis to prosim, tu tabulku a stavy. Mne to vyslo ako jemu... Je ta tabulka zla?

[johnyo13]

este ti chybaju prechody pre stav ABS, mne vznikli 2 ekv. stavy (AB,ABS)

Napis to prosim, tu tabulku a stavy. Mne to vyslo ako jemu... Je ta tabulka zla?

uz som to opravil, tam chybali len prechody pre novovzniknuty stav ABS

[zuzanka]

este ti chybaju prechody pre stav ABS, mne vznikli 2 ekv. stavy (AB,ABS)

Napis to prosim, tu tabulku a stavy. Mne to vyslo ako jemu... Je ta tabulka zla?

uz som to opravil, tam chybali len prechody pre novovzniknuty stav ABS

preco sa do tabulky nedavalo B?

[Killian]

este ti chybaju prechody pre stav ABS, mne vznikli 2 ekv. stavy (AB,ABS)

Napis to prosim, tu tabulku a stavy. Mne to vyslo ako jemu... Je ta tabulka zla?

uz som to opravil, tam chybali len prechody pre novovzniknuty stav ABS

A co dalej? Co tam je ekvivalentne? Vidim tam ze ABS a ABKS maju rovnake "riadky"... Ako to redukujem?

[zerg1986]

este ti chybaju prechody pre stav ABS, mne vznikli 2 ekv. stavy (AB,ABS)

Napis to prosim, tu tabulku a stavy. Mne to vyslo ako jemu... Je ta tabulka zla?

uz som to opravil, tam chybali len prechody pre novovzniknuty stav ABS

preco sa do tabulky nedavalo B?

Lebo je to nedosiahnutelny stav ... ak ho aj das do tabulky tak pri redukcii ho das prec

[ppt]

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?