VA ``='' reguláris nyelvtan

1. Legyen S = {a,b} és az L nyelvbe tartozzanak azok a szavak, melyekben mind az a, mind a b betűk száma páros, de a szó hossza nem osztható néggyel. Automata kívántatik aztán meg az automatához reguláris nyelvtan.

2. Most az ábécé a = {a,b,c}. Az L nyelv szavaira a következők igazak:

Minden szóban szerepel mindhárom karakter.
A szavak a-val kezdödnek és c-vel végzödnek.
Ha két szomszédos karakter nem egyforma, akkor a után csak b, b után csak c, c után csak a következhet. Készíts reguláris nyelvtant a fenti nyelvre, aztán alakítsd át a nyelvtant automatává! (Ha nemdeterminisztikus jön ki, akkor determinizáld!)

3. Legyen = {a,b} és az L nyelvbe tartozzanak azok a szavak, melyekben -ha van egyáltalán- a teljes homogén a-sorozatok hossza páratlan.

Szerkesszen az alábbi nyelvekre DVA-t: L, L², L    L², L^*.

4. Négy rokonnyelv karakterkészlete = {a,b}.
Az első nyelvbe azok a szavak tartoznak, amik a-val kezdődnek és b-vel végződnek és bennük minden teljes homogén részsorozat páratlan.

A második nyelvbe tartozó szavakra az a kikötés, hogy b-vel kezdődjenek és a-val végződjenek és bennük minden teljes homogén részsorozat legyen páratlan.

A harmadik nyelv az első kettő konkatenáltja, elöl áll az első nyelv.

A negyedik nyelv a harmadik tranzitív lezártja. Adjatok mind a négy nyelvre VA-t (szorgalmasak DVA-t)!

5. Legyen = {a,b} és az L nyelvbe tartozzanak azok a szavak, melyekben van páros (nemüres) teljes homogén részsorozat.

Szerkesszen a fenti nyelvre, a nyelv tranzitív lezártjára és önmagával való konkatenáltjára DVA-t!

6. Igaz-e, hogy ha L egy reguláris nyelv a felett, akkor az L^' = {  xy ^*   |  x    L, y nem   L  } nyelv is reguláris? Bizonyítás vagy ellenpélda kell.

Pumpálással

7. Reguláris-e az {  a^m bⁿ   |  m n 2m  } nyelv?

8. És ez reguláris-e? {  xx  |  x {a,b}^*  }

  
2VA ''='' sima VA

9. Legyen egy 2VA szabályrendszere a következő:
(S,a) = (P,j)
(S,b) = (Q,j)
(P,a) = (R,j)
(P,b) = (Q,j)
(Q,a) = (S,b)
(Q,b) = (S,j)
(R,a) = (P,j)
(R,b) = (P,b)

Kezdőállapot az S, elfogadó állapotok az S és a P.
Csinálj belňle egyirányú VA-t és határozd meg az elfogadott nyelvet!