Ćwiczenia 1 (4.X 2025)
-
Przykłady automatów skończonych. Niedeterministycznych. Z cichymi przejściami.
Automaty dla wyrażeń regularnych:
- a*ba*
- słowa parzystej długości
- kończące się sekwencją aba
- słowa z n-tą od końca literą a (niedeterministyczny na ok. n stanów, deterministyczny wymaga 10^n stanów)
- automat rozpoznający liczby binarne podzielne przez 6
Ćwiczenia 2 (18.X 2025)
-
Poniższe języki są nieregularne (lemat o pompowaniu), czy są bezkontekstowe? (jeśli tak to pokaż gramatykę):
- {a^k⋅b^l | k>l>0}
- {w| |w|_a=|w|_b} liczba wystąpień a i b w słowie
- {w| |w|_a=2⋅|w|_b} liczba wystąpień a i b w słowie
- {w| w=w^R} (palindromy)
- {a^p| p jest liczbą pierwszą} (nie jest bezkontekstowy, pompowanie dla bezkontekstowych tak samo tego dowodzi jak i dla regularnych)
- dobrze ustawione nawiasy
- δ(q_0,a)=q_0, δ(q_0,a)=q_1, końcowy q_1
- δ(q0,a)=q0, δ(q0,b)=q0, δ(q0,b)=q1, δ(q1,b)=q2, δ(q2,b)=q2, δ(q2,a)=q2, końcowy q_2
- δ(p,0)=q, δ(p,0)=s, δ(p,1)=q, δ(q,0)=r, δ(q,1)=q, δ(q,1)=r, δ(r,0)=s, δ(r,1)=p, δ(s,1)=p, końcowe q i s
