zagadnienia

2007-32-22

Dr hab. Tadeusz Krasiński

Zakład Analizy Rzeczywistej i Algebry⁷

Tematy na egzamin ustny do wykładu „Automaty i języki formalne” Studia stacjonarne Rok akademicki 2007/2008

1.    Alfabety i języki formalne. Przykłady.

2.    Operacje +, •. * na językach formalnych.

3.    Wyrażenia regularne. Przykłady.

4.    Języki regularne. Przykłady.

5.    Deterministyczne automaty skończone. Przykłady.

6.    Niedetermmistyczne automaty skończone. Przykłady,

7.    Niedeterministyczne automaty skończone z A-przejściami. Przykłady.

8.    Twierdzenie o równości zbioru języków: JDAS=JNAS.

9.    Twierdzenie o równości zbioru języków: JNAS=JNAS-A.

10.    Twierdzenie Kleenego.

11.    Operacje +, •,*, r\' na językach regularnych.

12.    Lemat o pompowaniu dla języków regularnych.

13.    Przykłady języków nieregularnych.

14.    Algorytmy decyzyjne dla języków regularnych.

15.    Konstrukcja minimalnego automatu.

16.    Algorytm wyznaczania minimalnego automatu.

17.    Gramatyki bezkontekstowe. Przykłady.

18.    Języki bezkontekstowe. Przykłady.

19.    Drzewa wyprowadzenia dla języków bezkontekstowych.

20.    Lewe i prawe wyprowadzenia w gramatykach bezkontekstowych.

21.    Gramatyki regularne.

22.    Postać normalna Chomsky’ego gramatyk bezkontekstowych.

23.    Operacje +, •,*, ry’ na językach bezkontekstowych.

24.    Lemat o pompowaniu dla języków bezkontekstowych.

25.    Przykłady języków, które nie są bezkontekstowe.

26.    Automaty ze stosem. Przykłady.

27.    Graf automatu ze stosem. Przykłady.

28.    Języki akceptowane przez automaty ze stosem. Przykłady.

29.    Maszyny Turinga. Przykłady.

30.    Języki rekursywnie przeliczalne.

31.    Graf maszy ny Turinga.

32.    Wielotaśmowe maszyny Turinga.

33.    Niedeterministyczne maszyny Turinga,

34.    Gramatyki frazowe.

35.    Języki kontekstowe.

36.    Automaty liniow'0 ograniczone,

37.    Hierarchia Chomsky’ego języków .

38.    Złożoność obliczeniowa maszyn Turinga i języków formalnych.

39.    Klasy złożoności obliczeniowej.

40.    Problemy NP-zupelne.

41.    SAT-problem