Informatyka UJ forum

SZCZUR

czy to cos na wazniaku "Języki, automaty i obliczenia" jest zgodne z forysiowym tokiem nauczania?

edit:

i czy to wystarczy czy czegos tam brakuje?

Rogal

Ja uczę się ze skryptu i z ważniaka - powinno starczyć.

SZCZUR

ma ktos jakiegoś linka/emule/torenta do tej ich ksiazeczki?

smas

Spectro

@SZCZUR:
Popatrz na autorów tych rzeczy z ważniaka :> .

kafex

@Spectro : eee po co ;P

dzendras

Zgrałem sobie na dysk ważniaka z TJA (na wypadek kłopotów z netem np). Wrzuciłem go do zip, jeśli chcecie, to się częstujcie:

[link widoczny dla zalogowanych]

Skrobocik

Krisowski

Czy takie rzeczy jak języki liniowe i języki kontekstowe i typu (0) bedą na egzaminie? Na ćwiczeniach ich nie było (ja bynajmniej nie pamiętam czegoś takiego :P ) ale nie wiem dokąd zaszedł wykład.

Ethlinn

Fen

ile ma trwać ten egzamin? bo coś słyszałem, że 2 godziny... prawda to? Zwykle takie testy trwały koło godzinki...

Rogal

Podobno ma być 100 pytań...

r4ku

prosze, niech ktos madry wytlumaczy mi algorytm konstrukcji minimalnego automatu dla zadanego jezyka regularnego, bo mnie krew zalewa juz :/

yuuu

hmm sama tez chetnie posłucham, tylko prosze o tłumaczenie dla debila bo specjalistycznego to mam pełno w skryptach p.F jak i przepisane do samo z powrotem na wazniaku :)

hansu

Dobra, sprobujemy, ale nie recze ze cos z tego zroumiecie bo ja sam nie do konca to czaje :/

Wezmy przyklad "konny z trabka" czyli jezyk L = {ab^n, n >= 0}

Kostruujemy relacje ro1 czyli kroimy zbior wszystkich slow (aka A* aka wolny monoid nad alfabetem A) na dwie klasy - slowa nalezace i nie nalezace do L. Otrzymujemy

ro1 = (a,ab,abb,abbb,...) -< 1 klasa
(1, aa, aaa,..., aba,ba, baba, dupa i bog wie co jeszcze :P) <- druga klasa

No i teraz chcemy te nasze klasy "kroic" wedlug pewnej zasady tak dlugo jak sie da. A zasada wyglada tak:
- wez dwa slowa z klasy
- doklej im na koncu jeden i ten sam symbol z alfabetu
- sprawdz czy slowa powstale w ten sposob leza w jednej klasie rownowaznosci
- powtorz kroki 2 i 3 dla wszystkich symboli alfabetu

Jesli dla choc jednego symbolu otrzymane slowa nie beda nalezec do tej samej klasy, to w nowej relacji "bazowe" slowa (te do ktorych doklejalismy) nie beda juz nalezec do tej samej klasy - ich klase trzeba bedzie "rozciac".

No i teraz powtarzamy ciecie, otrzymujac kolejne ro2, ro3 itd do momentu kiedy juz sie nie bedzie dalo rozciac - tak otrzymana relacja wyznaczy nam stany minimalnego automatu. Wracajac do naszego przykladu:

klasa (a,ab,abb,abbb,...): jezeli na koncu 2 dowolnych slow dokleimy b, to oba beda nalezec to tej klasy. Jezeli dokleimy a, to oba nie beda nalezec. Wiec jest ok i ta klasa sie nam nie "rozpada"

klasa druga: jezeli do 2 dowolnych slow nie bedacych postaci ab^n dokleimy na koncu b, to oba nowe slowa tez nie beda postaci ab^n. Podobnie, jesli na koncu dokleimy a. Z jednym wyjatkiem. Jezeli wezmiemy slowo puste i jakies dowolne inne slowo w z tej klasy i dokleimy na koncu a, to otrzymamy a i wa. a nalezy do 1 klasy, a wa do 2. Tak wiec nasza klase 2 musimy rozciac na dwie klasy - klase zawierajaca slowo puste i klase zawierajaca reszte. Otrzymujemy w ten sposob relacje ro2

(a,ab,abb,...)
(1)
(wszystko inne)

Zabieramy sie za konstrukcje ro3. Jednak na mocy tego co napisalem powyzej przy cieciu klas ro1, nie uda nam sie juz rozciac zadnej klasy ro2. Tak wiec ro2 == ro3.

No i przystepujemy do kontrukcji automatu. Kazda klasa wyzancza jeden stan. Strzalki pomiedzy stanami wyznaczamy nastepujaco: bierzemy dowolne slowo z klasy odpowiadajacej stanowi i doklejamy do niego jakis symbol alfabetu. Patrzymy do ktorej klasy wpadlo to nowe slowo i do takiego stanu prowadzimy strzalke. Nasz automat bedzie wiec wygladal:

r4ku

dzieki wielkie. ja juz umieram od tego tja :smt120

yuuu

alleluja! hansu jestes wielki :)

raku nie przejmuj sie nie jestes sam :> ja rozpusciłam sobie jakies tabletki co niby rozbudzaja ale cos czuje odwrotny efekt działania :PP
a to wszystko pewnie okaze sie na nic bo ja do Forysiow nie mam szczescia :P

Fidel

ja bym jednak stawial na algorytm z wazniaka ktory sie wydaje prostszy.. a tego konnego dalej nie rozumiem :P

dla przykladu {(a^n)(b^m) : n,m > 0 } A = {a,b}

najpierw robimy sobie L = a+b+ bo sa to slowa ktore mamy w jezyku.

pozniej robimy dla kazdego symbolu a z A:
a^(-1)L

gdzie a^(-1)L =def= {w z A* : aw nalezy do L}

czyli bierzemy:
a^-1L = a+b+ suma b+ (to pierwsze chyba jasne, drugie powstaje ze slow typu ab+) i oznaczamy ten zbior jako X.
b^-1L = 0 (zbior pusty) oznaczony jako Y bo nie ma takiej mozliwosci zeby ustawic b^-1 + reszta znaczkow z X tak zeby zniwelowac ^-1

wiadomo ze dla kazdego a^-1Y = 0 = Y

to teraz liczymy dla X
a^-1X = X bo z b+ nie powstanie nic nowego a z a+b+ mamy X
b^-1X = b+ suma 1 (dla slowa "b" powstaje nam 1)
oznaczamy ten zbior jako Z

teraz liczymy dla Z
a^-1Z = 0 = Y
b^-1Z = Z

nie mamy nowych stanow wiec koniec liczenia:

teraz funkcje przejscia sa postaci: f(X,a) = a^-1X czyli ze zbioru X znaczkiem a przechodzimy do zbioru ktory wczesniej obliczylismy i jakos oznaczylismy. np. dla naszego zadania: a^-1L = X a a^-1Z = Y

Stan poczatkowy to nasze L. za to problem jest ze stanami koncowymi bo trzeba sprawdzac wszytkie stany czy generuja takie slowa ktore naleza do jezyka.

no i teraz jak juz mam ywszystko obliczone to mozemy narysowac automat

r4ku

chcialbym sie upewnic: czy na stronie 46 wykladu, na koncu w podpunkcie 10 nie powinno byc epimorfizm zamiast homomorfizm?

yuuu

tak raku tam powinno byc epimorfizm, w skryptach tego błedu juz nie ma :> widac nie tylko my sie gubimy w tych wszystkich twierdzeniach :))

exeman

Ojejej, o czym wy mówicie, ja w ogóle nie wiem o co chodzi, ale jeszcze dużo czasu, poucze się jutro wieczór. :D

r4ku

jakich skryptach? ja mam tylko wyklad ten tamten :P

yuuu

mam prosbe, czy ktos mogłby wytłumaczyc prawa kongruencje syntaktyczna i zwykla kongruencje syntaktyczna.
skad sie biora definicje klas abstrakcji kazdej z nich dla jakiegos tam zadanego jezyka...bo ja nie widze tego ://
w zasadzie to ja juz nic nie widze... :/// ...ciemnosc :p

@raku: no tej wspaniałej ksiaze działa Wita i Marii :> ktora w wiekszosci jest przepisana an wazniaku :> to z czego Ty sie uczysz to w zasadzie to samo, tylko ze opisów do twierdzen i dowodow brak :>

hansu

@yuuu: Prawa kongruencja syntaktyczna to jest wlasnie ta relacja ktora dostajemy na koncu tego ciachania A*, ktore opisalem odnosnie algorytmu na minimalny automat. Innymi slowy, to jest taki podzial na klasy, ze jak wezmiemy klase i wybierzemy z niej dowolne 2 slowa i dokleimy im na koncu dowolny symbol z alfabetu, to wpadna do tej samej klasy.

Kongruencja syntaktyczna to to samo, tylko doklejamy symbole z przodu albo z tylu (tzn oba warunki musza byc spelnione)

yuuu

yhym, dzieki hansu, ja juz ide spac bo nie wiem co wiem a wiem tylko ze nic nie wiem :)