JĘZYKI FORMALNE I AUTOMATY
 
 

Wykład

Wykł.1 Wykł.2 Wykł.3 Wykł.4 Wykł.5 Wykł.6 Wykł.7 

E-LEARNING



Materiały do wykładu: JFiA-w.rar

Ćwiczenia

Ćw.1  Ćw.2  Ćw.3  Ćw.4  Ćw.5  Ćw.6  Ćw.7  Ćw.8 - kolokwium 


Wykład 1

Wprowadzenie. Niezbędne definicje. Rys historyczny. Opis formalny. Drzewa syntaktyczne. Drzewo rozbioru składniowego. Notacja BNF. Notacja Polska. Odwrotna Notacja Polska. Klasyfikacja Chomsky’ego

Wykład 2

Automaty. Deterministyczny Automat Skończony. Niedeterministyczny Automat Skończony. Dwukierunkowy Deterministyczny Automat Skończony. Automat Moore’a. Automat Mealy’ego. Maszyna Turinga. Automaty ze stosem

Wykład 3

Wyrażenia regularne

Wykład 4

Transformacje automatów skończonych. Eliminacja pustych przejść. Konstrukcja automatu deterministycznego odpowiadającego automatowi niedeterministycznemu. Usuwanie stanów nieosiągalnych. Konstrukcja DAS dla NAS z pustymi przejściami. Minimalizacja deterministycznych automatów skończonych.

Wykład 5

Gramatyki bezkontekstowe. Upraszczanie gramatyk. Usuwanie pustych produkcji. Usuwanie symboli bezużytecznych. Postać normalna Chomsky’ego. Faktoryzacja lewostronna. Redukcja bezpośredniej rekursji lewostronnej. Postać normalna Greibach. Automaty Ze Stosem dla Gramatyk Bezkontekstowych

Wykład 6

Klasy gramatyk LL i LR. Analiza zstępująca (top-down). Analiza wstępująca (bottom-up).

Wykład 7

Teoria Automatów a Teoria Złożoności Obliczeniowej. Klasy złożoności obliczeniowej


Ćw. 1

Automaty skończone i wyrażenia regularne.
Deterministyczny automat skończony. Niedeterministyczny automat skończony. Wyrażenia regularne.

Ćw. 2

Automaty skończone i wyrażenia regularne.
Wyrażenia regularne. Konstrukcja niedeterministycznych automatów skończonych. Minimalizacja automatów skończonych.

Ćw. 3

Gramatyki bezkontekstowe.
Gramatyka bezkontekstowa. Wyprowadzenia (lewostronne, prawostronne). Język bezkontekstowy. Upraszczanie gramatyk bezkontekstowych.

Ćw. 4

Gramatyki bezkontekstowe.
Usuwanie pustych produkcji. Usuwanie symboli bezuzytecznych. Faktoryzacja lewostronna. Postać Normalna Chomsky'ego.

Ćw. 5

Gramatyki bezkontekstowe.
Redukcja rekursji lewostronnej. Postać Normalna Greibach.

Ćw. 6

Gramatyki LL(0), LL(k), LR(0), LR(k). Gramatyki kontekstowe.

Ćw. 7

Maszyna Turinga, złozonosc obliczeniowa.

Ćw. 8

Kolokwium.
Proszę przynie¶ć ołówki i gumki, aby prace były czytelne.

Tematy zadań na kolokwium:
Kolokwium 1
  • wypisz przykladowe łańcuchy generowane przez podane wyrażenia regularne
  • skonstruuj niedeterministyczny automat skończony dla wyrażenia regularnego
  • skonstruuj NAS oraz wyrażenie regularne dla podanego zagadnienia
  • znajdz stany nierozróżnialne w podanym automacie
  • dokonaj konwersji NAS do DAS
    Nowa wersja wykladow - juz wkrotce

    Kolokwium 2
  • podaj produkcje gramatyk bezkontekstowych opisujacych podane łańcuchy
  • usuwanie pustych produkcji
  • usuwanie symboli bezuzytecznych
  • faktoryzacja lewostronna
  • redukcja rekursji lewostronnej
  • transformacja gramatyki do postaci normalnej Chomsky'ego
  • transformacja gramatyki do postaci normalnej Greibach (na 5.0)


    • Kolokwium 2012 

    
1. Podanie przykładowych łańcuchów, generowanych przez podane wyrażenie regularne.
2. Konstrukcja niedeterministycznego automatu skończonego dla wyrażenia regularnego.
3. Minimalizacja automatów skonczonych 
4. Konstrukcja produkcji gramatyk bezkontekstowych, opisujących podane łańcuchy 
5. Transformacja gramatyki do postaci normalnej Chomsky'ego 
6. Redukcja rekursji lewostronnej
(wszystko = 4.5) + transformacja do postaci normalnej Greibach (5.0).



    Literatura i zasoby:

    [0]  Wykład
    [1]  Hopcroft J.E., Ullman, J.D.: Wprowadzenie do teorii automatów, języków i obliczeń. Wydawnictwo Naukowe PWN, Warszawa 2003
    [2]  Forys M., Forys W.: Teoria Automatów i Języków Formalnych. Akademicka Oficyna Wydawnicza EXIT, Warszawa 2005
    [3]  Waite W. M., Goos G.: Konstrukcja Kompilatorów. Wydawnictwa Naukowo-Techniczne, Warszawa 1989
    [4]  Aho A. V., Sethi R., Ullman J. D.: Kompilatory - reguły, metody i narzędzia. WNT Warszawa 2002.



    opr. Adam Piórkowski, 2007
     pioro(at)agh.edu.pl