Automaty - języki i złożoność obliczeniowa
Grupa 1, wtorek, 14.15-15.45, sala A303
ZALICZENIE:
Można mieć 2 nieusprawiedliwione nieobecności w trakcie semestru
Laboratorium jest zaliczane na ocenę. Na końcową ocenę składają się:
-
2 kolokwia ( oba trzeba zdać na co najmniej 50 % )
-
Wejściówki
-
Prace domowe ( za nieodrobienie odejmowane są pkt. od kolokiwum )
Laboratorium nr 1. (21.02.2024): Słowa, alfabety, języki
Laboratorium nr 2. (28.02.2024): Języki regularne
Laboratorium nr 3. (06.03.2024): Automaty deterministyczne
Laboratorium nr 4. (13.03.2024): Automaty niedeterministyczne, determinizacja
Laboratorium nr 5. (20.03.2024): Lemat o pompowaniu
Laboratorium nr 7. (03.04.2024): Automaty ze stosem
Laboratorium nr 8. (10.04.2024): Parsery, drzewa wywodliwych słów
Przykłady automatów ze stosem:
zad1
zad1
zad2
zad2
zad3
Wyniki ze spr. nr 1 i nr 2
Zad z ćwiczeń:
Gramatyka S->AB, A->aA|ab, B->AB|b generuje język a^(k1)ba^(k2)b...a^(kn)bb dla ki>0, n>0 i możemy zauważyć, że
każde słowo wywodzimy następująco z ciągu: AAAAA...b, gdzie jedno A odpowiada za podsłowo a^(ki)b. Z tego wynika, że
każde słowo ma jeden wywód lewostronny, a więc gramatyka jest jednoznaczna. Tego typu zadania nie będzie na kolokwium, tzn. wykazywania, że gramatyka jest jednoznaczna.
Laboratorium nr 9. (17.04.2024): KOLOKWIUM
Wyniki
Rozwiązania
Poprawa: 9.05 (czwartek) o 12.30, salę podam później
Laboratorium nr 10. (24.04.2024): Maszyna Turinga - wstęp
Laboratorium nr 11. (8.05.2024): Maszyna Turinga z k taśmami
Laboratorium nr 12. (15.05.2024): TBA
Laboratorium nr 13. (22.05.2024): Spotkanie integracyjne
Laboratorium nr 14. (29.05.2024): TBA
