Gyakorlat, 13. hét: állapotgépek

Czirkos Zoltán · 2018.08.22.

Állapotgépek tervezése.

Állapotgépek. A feladatok megoldásának lényege az, hogy az állapotátmeneti táblát és a tevékenyságtáblát megalkotjuk: az állapotgépet megtervezzük. Ha ez megvan, akkor onnantól a kódolás már mechanikus. Egy olyan feladatnál, ahol több állapotátmenet is van, nem lehet csak úgy nekiugrani a kódolásnak! Ha a táblázat megalkotása után fejből írunk valami kódot, nem a tábla alapján, annak sincs semmi értelme. Az is értelmetlen, ha a kettőt fordított sorrendben csináljuk meg…

A tervezés után az állapotgépet mindenképpen le kell tisztázni egy állapottáblával. A gráfot nézve ugyan jobban lehet mélázgatni az állapotátmeneteken, a táblázat sokkal áttekinthetőbb, és biztosítja azt is, hogy semelyik átmenetet sem hagytuk ki. A kódolás során pedig kifejezetten jobb abból dolgozni.

Felkészülés a gyakorlatra:

1. Hatodik kis ZH

Ezen az órán van a hatodik kis ZH.

2. Hejesírásreform

Alább a labor „hejesírásreform” feladatának megoldását látjuk.

#include <stdio.h>

int main(void) {
    typedef enum LyAllapot {
        alap,
        l_volt,
        ll_volt
    } LyAllapot;

    LyAllapot all = alap;
    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
          case alap:
            if (c == 'l') all = l_volt;
            else putchar(c);
            break;
          case l_volt:
            switch (c) {
                case 'l': all = ll_volt; break;
                case 'y': putchar('j'); all = alap; break;
                default: printf("l%c", c); all = alap; break;
            }
            break;
          case ll_volt:
            switch (c) {
                case 'l': putchar('l'); break;
                case 'y': printf("jj"); all = alap; break;
                default: printf("ll%c", c); all = alap; break;
            }
            break;
        }
    }

    return 0;
}

Válaszoljunk az alábbi, működést és kódolást érintő kérdésekre!

  1. Mit csinál a program? Mi a bemenete, mi a kimenete?
  2. Milyen állapotátmenetek történnek a süllyed szó beolvasása közben?
  3. Miért használ enum-ot az állapot tárolására, miért nem int-et?
  4. Miért int a c változó típusa, miért nem char?
  5. Miért van úgy zárójelezve a getchar()-os kiejezés, ahogy? Nincs benne fölösleges zárójel?
  6. Hány karakter beolvasása történik a ciklus egy iterációjában?
  7. Állapotgépesnek lenne tekinthető az olyan program, ahol a switch()-en belül is van getchar()?
  8. Van valami oka, hogy néhol switch() van, néhol if()?
  9. Tetszik a forráskód tördelése a belső switch()-eknél, ahol egy sorban vannak a case címkék, a teendők és a break-ek?
Megoldás
  1. Ly betűket j-re cserél, hosszú lly-t jj-re. A szabványos adatfolyamokkal dolgozik.
  2. Az első bejövő l után l_volt, a második után ll_volt állapotba kerül. Az y beolvasásakor így kerül a vezérlés a szaml += 2 sorra.
  3. Mert így neve van az állapotoknak, és nem sorszáma. Sokkal olvashatóbb a forráskód.
  4. Mert az EOF konstans szándékosan kívül esik a char típus ábrázolási tartományán, és nem lenne ábrázolható char típusú változóban.
  5. Nincs, mindegyik kell. Ha nem lenne az értékadás körül zárójel, akkor a kifejezés az = és a != operátorok precedenciája miatt c = (getchar() != EOF) értelmű lenne, tehát nem a karakterkód, hanem az összehasonlítás eredménye kerülne a c változóba.
  6. Pontosan egyet, mert a ciklusfeltétel kiértékeléséhez egy getchar() hívás tartozik. Sehol máshol nem történik olvasás.
  7. Nem. Az állapotgép lényege, hogy az esemény (itt: a beolvasott karakter) és az előzőleg elért állapot (itt: az all változó) alapján döntünk a tevékenységről. Ezáltal új állapotba is kerülhetünk, egy következő esemény feldolgozását előkészítve.
  8. Így volt kényelmesebb, átláthatóbb – elvi oka nincsen.
  9. Erre a kérdésre értelemszerűen nincs mintamegoldás. :)

3. Grill

Tételezzük fel, hogy az előző program egy olyan bemenetet kap, amely 'l' betűre végződik. Mi történik ilyenkor? Kétféleképp is hibázhat a program, mi ez a kétféle hiba? Mely állapotátmeneteken keresztül jutunk el oda, és milyen bemenetek esetén hibázik a program?

Megoldás

A szövegfájloknál bevett szokás az, hogy a fájl legutolsó karaktere mindig egy újsor (\n) karakter. Ezt azonban sajnos nem mindenhol tartják be (és nem minden szövegszerkesztő tesz így).

Ha a fájl utolsó szava „grill” vagy „modell”, és utána még van egy újsor karakter, akkor minden kiíródik helyesen. Ha azonban az az újsor karakter hiányzik, akkor a fenti program sem működik tökéletesen (az amúgy tulajdonképp hibásnak tekinthető, de legalábbis szokatlan fájlra). Ilyenkor ll_volt állapotban fejeződik be a program, és a "ll" karaktersorozat nem jelenik meg a kimeneten. Ugyanez a helyzet az egy 'l' betűre végződő szavaknál, de ott nem kettő, hanem csak egy karakter marad el.

Javítsuk ki a programot kétféleképpen!

  • Először úgy, hogy az állapotgép ciklusából kilépés után megvizsgáljuk az állapotot, amelyben a program befejeződött, és attól függően elvégezzük még a szükséges teendőket.
  • Másodszor pedig úgy, hogy a fájl vége jelet is egy eseménynek tekintjük, amelyet fölveszünk az l, y és egyéb események mellé. Vegyük észre, hogy ehhez a kódot is jelentősen meg kell változtatnunk; az állapotgép ciklusának kilépési feltétele most az lesz, hogy fájl vége jelet kaptunk.
Megoldás

Az első módszerhez csak pár sorral kell kiegészíteni a programot:

/* lehet, hogy vannak "beragadt" l betuk */
switch (all) {
   case alap: break;
   case l_volt: printf("l"); break;
   case ll_volt: printf("ll"); break;
}

A második módszer pedig:

lyegyébEOF
alap→l_voltki: cki: c→fajlvege
l_volt→ll_voltki: "j"
→alap
ki: "l", c
→alap
ki: "l"
→fajlvege
ll_voltki: "l"ki: "jj"
→alap
ki: "ll", c
→alap
ki: "ll"
→fajlvege
fajlvege

Az érdekesebb helyeket felkiáltójel jelöli meg a kódban.

#include <stdio.h>

int main(void) {
    typedef enum LyAllapot {
        alap,
        l_volt,
        ll_volt,
        fajlvege
    } LyAllapot;

    LyAllapot all = alap;
    while (all != fajlvege) {   // !
        int c = getchar();  // !
        switch (all) {
          case alap:
            switch (c) {
              case 'l': all = l_volt; break;
              case EOF: all = fajlvege; break;  // !
              default: putchar(c); break;
            }
            break;
          case l_volt:
            switch (c) {
                case 'l': all = ll_volt; break;
                case 'y': putchar('j'); all = alap; break;
                case EOF: putchar('l'); all = fajlvege; break;  // !
                default: printf("l%c", c); all = alap; break;
            }
            break;
          case ll_volt:
            switch (c) {
                case 'l': putchar('l'); break;
                case 'y': printf("jj"); all = alap; break;
                case EOF: printf("ll"); all = fajlvege; break;  // !
                default: printf("ll%c", c); all = alap; break;
            }
            break;
          case fajlvege:
            /* nem lehet, csak compiler warning miatt */    // !
            break;
        }
    }

    return 0;
}

4. Mondatok nagybetűsítője

Írjunk állapotgépes programot, amely a beírt, csupa kisbetűkből álló szöveget úgy javítja ki, hogy minden mondat elején álló első betűt nagybetűre cseréli!

Megoldás

Mondat végét jelző írásjel után a következő betű nagybetű, de csak akkor, ha szóköz is jött. Figyelni kell, hogy az utána lévő szóköztől nem váltunk kisbetűs módra még! A gép alapállapota a nagybetűsítés, hiszen a bejövő szöveg legelső karaktere biztosan mondat elején van.

. ! ?szóköz, \negyéb
nagybetűki: cki: cki: toupper(c)
→kisbetű
kisbetűki: c
→mondatvége?
ki: cki: c
mondatvége?ki: cki: c
→nagybetű
ki: c
→kisbetű
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>

bool mondatvege_jel(int c) {
    return c == '!' || c == '.' || c == '?';
}

int main(void) {
    enum allapot {
        nagybetu,
        kisbetu,
        mondatvege
    } all;
    all = nagybetu;     /* kiindulo allapot */

    int c;
    while ((c = getchar()) != EOF) {
        switch (all) {
        case nagybetu:
            putchar(toupper(c));
            if (!mondatvege_jel(c) && !isspace(c))
                all = kisbetu;
            break;
        case kisbetu:
            putchar(c);
            if (mondatvege_jel(c))
                all = mondatvege;
            break;
        case mondatvege:
            putchar(c);
            if (isspace(c))
                all = nagybetu;
            else if (!mondatvege_jel(c))
                all = kisbetu;
            break;
        }
    }

    return 0;
}

5. Zárójeles szöveg

Írjunk állapotgépes programot, amelyik egy adott szövegből eltávolítja a (zárójelezett részeket). Előfordulhat, hogy a zárójelek tetszőleges mélységben egymásba vannak ágyazva (például így, mint ez a (zárójeles) szó).

Megoldás

Nem lehet megoldani véges számú állapotot tartalmazó állapotgéppel. Minden bezáró zárójel „)” esetén tudni kellene, hogy hány be nem zárt zárójel van még; ez annyiféle „(” utáni állapotot feltételez. A feladat szövege szerint pedig ezekből tetszőlegesen sok lehetne. Ellenben állapotváltozónak használhatunk egy int-et, amit növelünk és csökkentünk. Feltételezve, hogy az int nem csordul túl, így megoldható a feladat – de ez nem véges automata, nem rajzolható fel egy véges állapotátmeneti gráffal vagy állapottáblával.