Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Automata Theory and Language
Koordynator przedmiotu:
dr hab. inż. W?adys?aw Homenda
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
brak
Semestr nominalny:
5 / rok ak. 2009/2010
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia30h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
1. Algorithms and Data Structures 2. Introduction to logic and set theory
Limit liczby studentów:
Cel przedmiotu:
Provide the students with basic theoretical aspects of automata theory and formal languages
Treści kształcenia:
Regular expressions, context free, context sensitive and unlimited grammars, pumping lemmas, Ogden lemma. Turing machines, push-down automata, finite automata. Nondeterminism, deterministic simulation. Finite automata, regular expressions, equivalence of both notions. Pumping lemma, Myhill–Nerode theorem, equivalence of regular expressions and finite automata, Myhill-Nerode theorem. Equivalence of push down automata and context free languages. Chomsky hierarchy.
Metody oceny:
· Admission to examination requires getting a pass of two written test (November and January, passing any test requires at least 26 out of 50 points) or – in case of failure of any one – a pass of written part of examination. Admission should be gained in the current academic year, · Examination consists of two parts: written (50 points) and oral (50 points). Passing any part requires at least 26 points out of 50. Absence or failure of any part of examination obligates undertaking both parts again. Student can repeat examination only once. Dates of examination are stated by dean’s office: two terms in January/February and one term in September. Grades: D for less than 52 points, C for 52-60, C+ for 61-70, B for 71-80, B+ for 81-90, 5 for 91 and more points
Egzamin:
Literatura:
1. Hopcroft J.E. Ullman J.D., Introduction to automata theory, languages and computation, 2. Homenda W., Elementy lingwistyki matematycznej i teorii automat?w, WPW
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się