Informatyka UJ forum

chlebek

Czy ktos moze mi powiedziec, czy robie cos zle , czy w testach jest blad ?

Pytania sa nastepujace:
1) Wskaz problemy nierozstrzygalne w klasie l2:
L1 c L2( gdzie tutaj L1 i L2 to dwa jezyki klasy l2 ) Prawda/Falsz ?
L1 u L2 e l2

2) Wkaz teze Churcha
Kazdy jezyk akceptowany przez maszyne Turinga jest typu 0. Prawda/Falsz ?

3) Czy jezyk jest bezkontekstowy ?
a^n b^m c^k gdzie k != m+n

hansu

Wedlug mnie:

2) Nie
3) Nie

chlebek

wedlug testu:
1) nie
tak
2) nie
3) tak

exeman

W jaki sposób sprawdzić szybko, że 3 jest tak lub nie?

hansu

Lemat o pompowaniu

exeman

Ale to wcale nie wychodzi szybko i sprawdza się tylko przy obalaniu.

rafal

3 jest Tak. Ten język jest bezkontekstowy, można łatwo wskazać automat ze stosem, który go akceptuje (zapamiętujesz na stosie ile było a, potem ile było b, a potem ściągasz przy kolejnych c i jeśli coś zostanie na stosie to znaczy, że k != m+n czyli akceptujesz, a w przeciwnym przypadku nie akceptujesz -- to tak w skrócie). A lemat o pompowaniu to tylko przy obalaniu, no i jest to trochę roboty zazwyczaj. Najlepiej przypatrzyć się językom, które występują w teście, na ważniaku, były na ćwiczeniach i zapamiętać jakie one były, bo wątpię,żeby na teście pojawiły się jakoś bardzo różniące się przypadki (a sprawdzanie każdego z osobna pod tym kątem może zająć trochę czasu).

Fidel

Kazda gramatyka regularna jest rozszerzajaca? Prawda/Falsz

w jednym tescie jest prawda w drugim falsz :) to jak jest w koncu?

rafal

Nie każda. Gramatyka regularna: v0 -> 1, v1 -> v0 jest regularna, ale nie jest rozszerzająca. (Brakuje założenia, że jeśli v -> 1 to wtedy v nie występuje po prawej stronie żadnego prawa)

Rogal

Coś czuję, że nas Darth Maria jutro tak skongruuje syntaktycznie że się nie pozbieramy..

Spectro

Hmm... chyba czas się zacząć uczyć 8) .

exeman

Mam pytanie:

Każda gramatyka bezkontekstowa jest kontekstowa. - FAŁSZ

Dlaczego fałsz?

hansu

Chyba dlatego ze kontekstowa nie moze zawierac produkcji wymazujacych dla nieterminala innego niz glowa, a bezkontekstowa moze...

exeman

Dzięki. To ostatnie pytanie w tej serii - jak łatwo sprawdzić czy dany język jest deterministyczny, a jak jednoznaczny? I czym one się różnią, bo to mi się strasznie miesza :/

dzendras

Deterministyczny - czy istnieje deterministyczny automat ze stosem, który go rozpoznaje. Z tego co wiem, to na pewno niedeterministycznym językiem będzie taki, który jest sumą mnogościową jakichś języków

Jednoznaczny - istnieje gramatyka jednoznaczna generująca ten język. Tutaj nie mam metody, robię "na czuja".

Fidel

exeman

Moim zdaniem to bez sensu, przecież każdy język można rozbić na sumę...

Ethlinn

kg86

zna ktos jakas sprawniejsza metode wyznaczania monoidu przejsc, inna niz robienie tej tabelki i sprawdzanie kolejno dla poszczegolnych slow? :)

exeman

Ta tabelka idzie bardzo szybko, korzystajac z wlasnosci, ze T(ab) = T(b) o T(a).

dzendras

Ethlinn: Wskazany przez Ciebie język jest niedeterministyczny (niepusta część wspólna) natomiast nie wiem jak określić jego jednoznaczność. Nie próbowałem bawić się w konstruowanie tej gramatyki, ale jeśli założymy, że język a^n b^n c^n tworzymy jednoznacznie oraz że obydwie gałęzi drzewa wywodu (dla pierwszego języka i drugiego) są również jednoznaczne, to język taki jest jednoznaczny. Udowodnij mi więc, że nie można zrobić jednego wywodu dla części wspólnej, to przychylę się do Twojej tezy :)

@Fidel: To chyba jednak nie zachodzi. Chociażby a^n b^m + c^k d^j. Taki język na pewno jest deterministyczny. Czyli skłaniałbym się ku spostrzeżeniu Ethlinn: mamy niepusty iloczyn języków => język będący ich sumą jest niedeterministyczny

SZCZUR

wpadłem na głupi pomysl pozbierania wszystkich wzorów i definicji z wazniaka. ale przy czwartym wykładzie straciłem juz chęci jak sie to komuś przyda to tu jest: [link widoczny dla zalogowanych]

ZenonZajebich

Ważniak, Test 8, zad 5
Tam jest, że prawidłowe jest 'a', a moim zdaniem powinno być 'b', bo przecież 1 należy do języka i 2k - 2l = 0 mod 2...
Może mi ktoś wytłumaczyć czy dobrze myśle?

yuuu

hmm no masz racje, przy załozeniu ze k i l > 0 słowo 1 nie jest uwzgledniana w tym jezyku a jednak mozna ja wyprodukowac :> w koncu wszedzie sa *

SZCZUR

podziwiam ze robice te testy ze zrozumieniem, ja mam zamiar sie ich nauczyc na pamiec i moze jakos to bedzie:)