Module also offered within study programmes:
General information:
Name:
Języki Formalne i Automaty
Course of study:
2015/2016
Code:
BIT-2-106-OB-s
Faculty of:
Geology, Geophysics and Environmental Protection
Study level:
Second-cycle studies
Specialty:
Software and Data Bases in Geology
Field of study:
Applied Computer Science
Semester:
1
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. inż. Piórkowski Adam (pioro@agh.edu.pl)
Academic teachers:
Module summary

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Student ma kompetencje do konstrukcji gramatyk dla zadanych problemów przetwarzania danych i kompilacji IT2A_K06 Execution of exercises
Skills
M_U001 Student powinien umieć stosować przekształcenia i uproszczenia dla automatów skończonych oraz dla gramatyk IT2A_U07 Execution of exercises
Knowledge
M_W001 Student zna klasyfikację Chomsky’ego IT2A_W08 Execution of exercises
M_W002 Student zna definicje i podstawowe własności automatów skończonych IT2A_W08 Execution of exercises
M_W003 Student zna teorię wyrażeń regularnych i języków bezkontekstowych IT2A_W08 Execution of exercises
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Student ma kompetencje do konstrukcji gramatyk dla zadanych problemów przetwarzania danych i kompilacji - + - - - - - - - - -
Skills
M_U001 Student powinien umieć stosować przekształcenia i uproszczenia dla automatów skończonych oraz dla gramatyk - + - - - - - - - - -
Knowledge
M_W001 Student zna klasyfikację Chomsky’ego + - - - - - - - - - -
M_W002 Student zna definicje i podstawowe własności automatów skończonych + - - - - - - - - - -
M_W003 Student zna teorię wyrażeń regularnych i języków bezkontekstowych + - - - - - - - - - -
Module content
Lectures:

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

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

Wyrażenia regularne

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.

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

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

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

Auditorium classes:

1.Automaty skończone i wyrażenia regularne. Deterministyczny automat skończony. Niedeterministyczny automat skończony. Wyrażenia regularne.
2. Automaty skończone i wyrażenia regularne. Wyrażenia regularne. Konstrukcja niedeterministycznych automatów skończonych. Minimalizacja automatów skończonych.
3. Gramatyki bezkontekstowe. Gramatyka bezkontekstowa. Wyprowadzenia (lewostronne, prawostronne). Język bezkontekstowy. Upraszczanie gramatyk bezkontekstowych.
4. Gramatyki bezkontekstowe. Usuwanie pustych produkcji. Usuwanie symboli bezuzytecznych. Faktoryzacja lewostronna. Postać Normalna Chomsky’ego.
5. Gramatyki bezkontekstowe. Redukcja rekursji lewostronnej. Postać Normalna Greibach.
6. Gramatyki LL, LR. Gramatyki kontekstowe.
7. Maszyna Turinga, złozonosc obliczeniowa.

E-learning:
-
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 60 h
Module ECTS credits 2 ECTS
Participation in lectures 15 h
Realization of independently performed tasks 15 h
Participation in auditorium classes 15 h
Preparation for classes 15 h
Additional information
Method of calculating the final grade:

Ocena końcowa = 100% oceny z ćwiczeń

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:

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.

Scientific publications of module course instructors related to the topic of the module:

Additional scientific publications not specified

Additional information:

None