Informatyka UJ forum

aga

Ryzykuję, jakby ktoś chciał moje kolokwium, to będę je miała jutro ze sobą.

ZenonZajebich

fen :
czy ktoś może rozwiązać zadanko:
znajdź automat minimalny dla języka L = (a+b)a((a+b)^2)*

Krisowski

L = (a+b)a((a+b)^2)*
Konstrukcja automatu minimalnego:

Crow

Moim zdaniem tutaj (i na cwiczeniach byl blad):

wezmy dwa slowa z klasy: (a+b)a((a+b)^2)*(a+b)
dokladniej:
(a+b)a((a+b)^2)*a i (a+b)a((a+b)^2)*b

Jesli do obu dodamy a to pierwsze trafi do jezyka a drugie.... no wlasnie gdzie? IMHO brakuje tutaj jeszcze jednej klasy do ktorej trafiloby to drugie slowo. Zreszta... jesli narysujesz sobie graf na podstawie tych 5 stanow z cwiczen a nastepnie sprawdzisz dla dowolnego slowa z jezyka to latwo zauwazyc ze cos jest jednak nietak.

Krisowski

Też się kiedyś nad tym zastanawiałem. Doszedłem do wniosku, że chodzi tu o interpretację (a+b)^2 .
Jeśli zinterpretujesz to jako dowolne słowo o długości dwa {aa, ab, ba, bb} to rozwiązanie z ćwiczeń (i moje) jest poprawne, bo jak weźmiesz te dwa słowa:
(a+b)a((a+b)^2)*a i (a+b)a((a+b)^2)*b
to cokolwiek byś nie dopisał będzie miało znów parzystą długość.

Znów nie wiem, czy mam rację, ale przyjmuję, że dr Foryś nie pomyliła się na ćwiczeniach i tak to sobie tłumaczę ;) .

Crow

hmm... mnie sie wydaje ze:

(a+b)^2 = (aa | bb)

EDIT:

chociaz chyba masz racje... ale prosilbym kogos o potwierdzenie

EDIT2:

Potwierdzam... mam w zeszycie zapisane ze: ((a+b)^2)* = (ab + ba + bb + aa)*

:P

kg86

a propo minimalizacji automatow :) moglby ktos wytlumaczyc tak na chlopski rozum na czym polega konstrukcja automatu minimalnego z jakiegos innego automatu? :) tzn. w jaki sposob trzeba rozdzielac na grupy te stany? ktore beda poczatkowe, ktore koncowe i kiedy trzeba przestac je rozdzielac? :)
btw. nie pytam o ta metoda z trojkatna tabelka, tylko o metode ze zwykla tabelka stanow ;)

EDIT: ok, juz nie trzeba, sam skumalem :P

aga

Podobno nadchodzi kolokwium, więc...

Kolokwium 2 (2006)

(1) Wykorzystując lemat o pompowaniu udowodnij że język L = {w(odbicie zwierciadlane(w))w : w e {a,b}*} nie jest językiem bezkontekstowym (3 pkt)

(2) Określ automat ze stosem akceptujący język L = {a^nb^ma^pb^q : n=m lub p=q, n,m,p,q>=1}
(a) Czy język L jest językiem deterministycznym? (4 pkt)
(b) * Czy język L jest językiem jednoznacznym? (2 pkt)
(c) * Określ najmniejsze k takie że język L e L k lin (2 pkt)

(3) Rozwiązując stowarzyszony układ równań określ wyrażenie regularne reprezentujące język L(G), gdzie G = ({v0,v1,v2},{a,b},v0,P)
P = {v0->av1, v0->bv2, v0->1, v1->bv0, v1->av2, v2->av0,v2->bv1} (2 pkt)

@Spectro: tylko nie dziękuj:P

Spectro

ZenonZajebich

Wie ktoś moze o co chodziło w zadaniu z ostatnich ćwiczeń które robił makros?
Bo siedzimy z kapuhem, próbujemy rozkminić to dziadostwo i ni hu hu...
Chodzi o to takie z trójkami...

Makros

dobra.. apropo trzeciego od Agi...:
To mi wyszło tak:

v0 = [ (a+b^2) (ab)* (b+a^2)]* + 1

Tylko mi nie mówić, że źle mam... bo taki ładny wynik... :P

Fen

jak dojdę do tego tematu to Ci odpowiem ;p

Spectro

@Makros:
Źle masz :P . A przynajmniej ja nie widzę, jak można z tej postaci uzyskać słowo "ba", które łatwo otrzymać przez v0 -> bv2 -> bav0 -> ba .

Mi wyszło: (aa*b + ba + bba*b)*

Makros

bo głupi jestem i się pomyliłem przy przepisywaniu do linijki niżej.. :P

mam tak:

v0 = [ (a+b^2) (ab)* (b+a^2) + ba]*

kurcze... chyba to policzę jeszcze raz...

edit:

a z Twojego można niby zrobić: bbab :P albo aab :p

Spectro

A z Twojego "bbaa" :lol: .

edit:
Oczywiście, że tamte słowa da się zrobić. Chyba, że widzę inne produkcje :p .

edit2:
Faktycznie widzę inne produkcje :x . Robię to jeszcze raz.

Makros

Spectro

Ostatecznie, przy już właściwych produkcjach, wyszło mi to samo... Ale to trochę trwało, zanim wymyśliłem najprostszą formę wyliczeń (wyznaczamy kolejno: v1(v0), v2(v0) i ostatecznie v0).

Makros

ad 2. czy ten język akceptuje a^n b^m a^p b^q n=m i p=q... ? w sumie tam jest napisane "lub" a nie "albo"... wiec... ?

edit:

nikt nie wie... ?

Crow

a maszyna Turinga bedzie?

Makros

Ze tak powiem... Dobre pytanie...

Wie ktoś... ?

hansu

Maszyna Turinga jest absolutem - ona jest wszedzie :D

kg86

maszyna turinga z tego co pamietam moze sie pojawic :P
ale to jest proste :) WDI nie pamietacie? :P

Fen

w sumie lepsza maszynka Turinga niż jakiś dowodzik :D
a z tego co pamiętam na WDI (u dr Kawy) to robiliśmy bardziej zaawansowane maszyny niż te co na ostatnich ćwiczeniach z Marysia :)

kg86

moglby ktos (kto jeszcze nie spi) wyjasnic mi roznice miedzy automatem, ktory akceptuje jezyk przez stany koncowe, oraz przez pusty stos? :)
EDIT: nie trzeba :) znalazlem przyklady :) ech... brac sie o 23 za TJA, to jednak bylo troche za pozno :P

Fen

no sam nie wiem jak to będzie... może się uda zdobyć koło 6pk, więc może jakimś cudem zalkę dostanę...
jak zwykle głupie błędy plus dość trudne jedno zadanie...

oby Maria byłą dla nas łaskawa...