2. Az L = {0ⁱ1^j2^j   |  i 1, j 1} nyelv nem reguláris. Bizonyítsd be ezt!

Nehéz! Érdekességnek egy feladat, ami szintén a pumpáláshoz kapcsolódik:

Bizonyítsuk be, hogy az L={ xx^-1w | x {a,b}⁺, w {a,b}^*}.

3. Minimálautomata kéretik az alábbi DVA-hoz!
(A,0)= E
(A,1)= B
(B,0)=C
(B,1)=B
(C,0)=D
(D,1)=D
(E,0)=F
(F,1)= D

Kezdő az A, elfogadók a D és az F.

4. Ehhez is!
(A,a)= E        (E ,a )=H
(A ,b )=C        (E ,b )=F
(B ,a )= H        (F ,a )=F
(B ,b )= A        (F ,b )=D
(C ,a )=C        (G ,a )=D
(C ,b )=G        (G ,b )=F
(D ,a )=D        (H , a)=H
(D ,b )=H        (H ,b )=H

Kezdő az A, elfogadók a C, D, F, G és a H.

5. És ehhez is.

(a,0)= b        (e ,0 )=d
(a ,1 )=a        (e ,1 )=f
(b ,0 )= a        (f ,0 )=g
(b ,1 )= c        (f ,1 )=e
(c ,0 )=d        (g ,0 )=f
(c ,1 )=b        (g ,1 )=g
(d ,0 )=d        (h , 0)=g
(d ,1 )=a        (h ,1 )=d

Kezdő az a, elfogadó a h.

6. DVA kell az alábbi kifejezésekre:
(a) 10+(0+11)0^*1

(b) 01[((10)^*+111)^*+0]^*1

7. Reguláris kifejezés kell az automatához!
(A,0)= B
(A,1)= C
(B,0)=A
(B,1)=C
(C,0)=B
(C,1)=A
Kezdő az A, végállapotok a B és a C.

8. Ehhez szintén.
(A,0)= B
(A,1)= C
(B,0)=A
(B,1)=C
(C,0)=D
(C,1)=B
(D,0)=C
(D,1)= B
Kezdő az A, végállapotok az A és a C.

9. Most meg ehhez a nyelvtanhoz kell reguláris kifejezés!

S1A | 0B, A0A | 1A | 1, B0B | 1B | 0.

  
10. Írd le reguláris kifejezéssel az alábbi nyelveket! (Esetleg adj a reguláris kifejezéshez DVA-t is!)

(a) Az ábécé a {0,1}. A nyelvbe azok a szavak tartoznak, melyekben a 0-k és 1-ek száma megegyezik és amelyek minden prefixében a 0-k és az 1-ek számának különbsége maximum 1.

(b) Az ábécé ugyanaz mint az előbb. A nyelv szavai olyanok, hogy bennük max. egy legalább kettő hosszú homogén részsorozat van.