Wydział Matematyki i Informatyki - Teoria Obliczeń i Złożoności - Ćwiczenia Arkusz 7 - WŁASNOŚCI JĘZYKÓW REGULARNYCH

Zadanie 1. Udowodnij, że dla dowolnych języków regularnych L 1, L 2, ich różnica L 1 \L 2 jest językiem regularnym.

Zadanie 2. Udowodnij, że jeśli L 1 jest językiem nieregularnym oraz L 2 i L 1 ∩ L 2 są językami regularnymi, to L 1 ∪ L 2 jest językiem nieregularnym.

Zadanie 3. Wykaż, że następujące języki nie są regularne:

a) L = {a 2 nbn : n ∈ N }

b) L = {anbnan : n ∈ N }

c) L = {anban : n ∈ N }

d) L = {ap : p jest liczba pierwszą }

e) PALINDROMY

f) L = {AA : A ∈ {a, b}∗}

g) MNOŻENIE = { 0 i 10 j 10 ij : i, j ∈ N }

h) L = {anbmck : n + m = k, n, m, k ∈ N }

Zadanie 4. Wykaż, że język L = {an : n nie jest liczbą pierwszą }

a) nie jest językiem regularnym

b) spełnia warunki tezy lematu o pompowaniu z wyjątkiem warunku (1).