Języki, automaty i obliczenia/Ćwiczenia 4: Wyrażenia regularne. Automat minimalny

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 4

Ćwiczenie 1

Pokaż, że każdy skończony zbiór słów nad dowolnym alfabetem jest regularny, tzn. jest określony przez pewne wyrażenie regularne.

Rozwiązanie

Ćwiczenie 2

Sprawdź, czy język ciągów binarnych, w których sekwencja 11 występuje dokładnie raz, da się określić wyrażeniem regularnym.

Rozwiązanie

Ćwiczenie 3

Udowodnij równoważności wyrażeń regularnych (, i są dowolnymi wyrażeniami regularnymi).

(1) ,
(2) ,
(3) ,
(4) ,
(5) ,
(6) .
Rozwiązanie punktu 1
Rozwiązanie punku 2
Rozwiązanie punktu 3
Rozwiązanie punktu 4
Rozwiązanie punktu 5
Rozwiązanie punktu 6

Ćwiczenie 4

Udowodnij, że dla dowolnych wyrażeń regularnych , i wyrażenia

nie są równoważne.

Rozwiązanie

Ćwiczenie 5

Sprawdź, czy następujące wyrażenia regularne są równoważne ( oraz są dowolnymi wyrażeniami regularnymi.)

(1) ,
(2) ,
(3) ,
Rozwiązanie punktu 1
Rozwiązanie punktu 2
Rozwiązanie punktu 3

Ćwiczenie 6

Określ za pomocą wyrażeń regularnych następujące języki:

(1) wszystkie czteroliterowe słowa nad alfabetem ,
(2) wszystkie trzyliterowe słowa nad alfabetem , w których występuje dokładnie jedna litera ,
(3) wszystkie słowa o dowolnej długości nad alfabetem , w których występuje dokładnie jedna litera ,
(4) język poprawnych adresów stron www, jeśli założymy, że poprawny adres strony www składa się ze słowa ".", a następnie ciągu liter i cyfr zawierającego przynajmniej jedną kropkę, przy czym ostatnim znakiem tego ciągu nie może być kropka.
(5) ogół sekwencji binarnych, w których liczba zer jest podzielna przez 3,
Rozwiązanie punktu 1
Rozwiązanie punktu 2
Rozwiązanie punktu 3
Rozwiązanie punktu 4
Rozwiązanie punktu 5

Ćwiczenie 7

Niech będzie językiem określonym przez wyrażenie regularne nad alfabetem . Określ prawą kongruencję syntaktyczną i kongruencję syntaktyczną dla tego języka.

Rozwiązanie

Ćwiczenie 8

Wykorzystując ciąg relacji zdefiniowanych w twierdzeniu 3.3 w wykładu 4 (patrz twierdzenie 3.3 wykład 4) określ prawą kongruencję syntaktyczną dla następujących języków.

(1)
(2)
Rozwiązanie punktu 1
Rozwiązanie punktu 2

Ćwiczenie 9

Zdefiniuj minimalny automat akceptujący następujące języki:

(1)
(2)
Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 10

Udowodnij równoważności wyrażeń regularnych (, i są dowolnymi wyrażeniami regularnymi).

(1) ,
(2) ,
(3) ,
(4) ,

Ćwiczenie 11

Sprawdź, czy następujące wyrażenia regularne są równoważne ( oraz są dowolnymi wyrażeniami regularnymi.)

(1) .
(2) ,
(3) ,
(4) ,
(5) .

Ćwiczenie 12

Określ za pomocą wyrażeń regularnych następujące języki:

(1) ogół sekwencji binarnych, w których występują co najwyżej trzy zera,
(2) ogół sekwencji binarnych, w których występują co najwyżej dwa zera obok siebie,
(3) ogół sekwencji binarnych, w których liczba zer jest podzielna przez dwa, a liczba jedynek przez 3,
(4) język poprawnych adresów e-mail. Dla uproszczenia przyjmujemy, że poprawny adres e-mailowy składa się z niepustego identyfikatora złożonego z samych liter (maksymalnie z czterech), znaku "małpy", niepustej nazwy serwera złożonej z samych liter (maksymalnie czterech), kropki oraz dwuliterowej nazwy domeny. Alfabet składa się tylko z liter , i .

Ćwiczenie 13

Wykorzystując ciąg relcji zdefiniowanych w twierdzeniu lekcja4-w-tw? określ prawą kongruencję syntaktyczną dla następujących języków.

(1)
(2)

Ćwiczenie 14

Zdefiniuj minimalny automat akceptujący następujące języki:

(1)
(2)