Wydział Matematyki i Informatyki - Teoria Obliczeń i Złożoności - Ćwiczenia Arkusz 6 - TWIERDZENIE KLEENE’EGO

Zadanie 1. Skonstruuj, metodą z dowodu twierdzenia Kleene’ego, automaty skończone akceptujące następujące języki:

a) L( ab∗)

d) L( a∗ba∗ + b∗) g) L(( a + b) a∗ba∗) b) L( a + b∗)

e) L(( a∗ba∗ + b∗)( aa∗)) c) L( ab∗ + a)

f) L(( a∗ba∗ + b∗) ∗) h) L(( a∗b + b∗a) ∗) Zadanie 2. Metodą z dowodu twierdzenia Kleene’ego znajdź wyrażenia regularne generujące języki akceptowane przez przedstawione automaty:

a)

e)

b)

f)

c)

g)

d)