Teoria automatów i języków formalnych

RSS

Cel przedmiotu

Celem wykładu jest zapoznanie studentów z teorią automatów i języków formalnych. Wprowadzane są podstawowe pojęcia, dokonywana jest klasyfikacja języków formalnych, omawiane jest definiowanie języków, budowa automatów akceptujących języki oraz ich zastosowanie w kontekście zagadnień translacji będących przedmiotem kursu teorii kompilacji na III roku.

Program wykładu

Język naturalny a język formalny. Definiowanie języka formalnego. Pojęcia i operacje podstawowe. Klasyfikacja Chomsky’ego. Gramatyka bezkontekstowa, jednoznaczność gramatyki. Rozbiór gramatyczny. Niedeterministyczny i deterministyczny automat ze stosem. Automat ze stosem a gramatyka bezkontekstowa. Od gramatyki bezkontekstowej do automatu ze stosem. Postaci normalne gramatyk bezkontekstowych. Własności zamkniętości języków bezkontekstowych. Technologie parsingu. Algorytm Cocke’a-Youngera-Kasamiego. Wyrażenia regularne, języki regularne. Deterministyczny (DFA) i niederministyczny (NFA) automat skończony. Gramatyka regularna. Od wyrażenia regularnego do DFA. Twierdzenie Myhilla-Nerode’a. Minimalizacja automatu skończonego. Od DFA do wyrażenia regularnego i gramatyki regularnej. Własności zamkniętości języków regularnych. Języki kontekstowe i automaty liniowo-ograniczone. Deterministyczne i niedeterministyczne maszyny Turinga. Języki rekurencyjne i rekurencyjnie przeliczalne. Problemy nierozstrzygalne. Języki nie będące rekurencyjnie przeliczalnymi.

Charakterystyka pozostałych zajęć

W przedmiocie prowadzone są ćwiczenia audytoryjne. Treści tych zajęć ugruntowują i rozszerzają wiedzę przekazywaną podczas wykładów. Rozwiązywane są zadania, dowodzone są niektóre rezultaty teoretyczne. Szczególną uwagę zwraca się na zagadnienia teoretyczne rozwiązywane z wykorzystaniem podejścia algorytmicznego, jak np. algorytmy decyzyjne dla języków bezkontekstowych i regularnych, dowodzenie w oparciu o lematy o pompowaniu, przekształcenia gramatyk, automatów i wyrażeń regularnych, klasyfikowanie gramatyk i języków z wykorzystaniem hierarchii Chomsky’ego, projektowanie gramatyk i automatów dla zadanych języków formalnych.

Bibliografia

1. A. V. Aho, Sethi R., Ullman J.D.: Compilers. Principles, techniques, and tools, Addison, 2006
2. Homenda W.: Elements of mathematical linguistics and automata theory, Publishing House of Warsaw University of Technology, 2005
3. Hopcroft J. E., Motwani R., Ullman J.D.: Introduction to automata theory, languages, and computation, Addison Wesley, 2006
4. KA Ross, CRB Wright: Discrete Mathematics, PWN, 1996
5. M. Sipser: Introduction to the theory of computation, WNT, 2009

Wszelkie prawa zastrzeżone © 2010 Katedra Informatyki   |   Akademia Górniczno-Hutnicza   |   Realizacja Creative Bastards