Języki, automaty i obliczenia/Ćwiczenia 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 7

Ćwiczenie 1

Niech . Dla automatów

gdzie

skonstruuj automat taki, że
Rozwiązanie

Ćwiczenie 2

Niech . Dla automatu

gdzie

a funkcja przejść zdefiniowana jest następująco:

skonstruuj automat deterministyczny taki, że

Wskazówka
Rozwiązanie

Ćwiczenie 3

Dane są dwa automaty nad tym samym alfabetem
i . Udowodnij, że istnieje liczba taka, że jeśli dla każdego słowa o długości spełniona jest implikacja , to

Rozwiązanie

Ćwiczenie 4

Niech będzie dowolnym alfabetem, a językiem regularnym. Udowodnij, że język jest też językiem regularnym.

Rozwiązanie

Ćwiczenie 5

Udowodnij, że następujące języki nie są regularne:

  1. ,
  2. .
Rozwiązanie punktu 1
Rozwiązanie punktu 2
ZADANIA DOMOWE

Ćwiczenie 6

Niech . Skonstruuj automat , taki że

1. gdzie


2. gdzie


Podaj dwie konstrukcje:

  1. opartą na dowodzie twierdzenia Kleene'ego,
  2. z wykorzystaniem automatu z pustymi przejściami.

Ćwiczenie 7

Skonstruuj minimalny automat , taki że , gdzie opisany jest

poniższym grafem:
Rysunek 5


Ćwiczenie 8

Udowodnij, że następujące języki nie są regularne:

  1. ,
  2. .
Wskazówka do punktu 2

Ćwiczenie 9

Zbuduj automat akceptujący język będący ogółem skończonych sekwencji binarnych, w których liczba zer jest podzielna przez dwa, a liczba jedynek przez 3, a następnie gramatykę generującą ten język.

Wskazówka