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

Czirkos Zoltán, Pohl László · 2017.07.26.

Állapotgépek.

Felkészülés a laborra:

1. Haladási napló, ZH jelentkezés

Haladási napló, ZH jelentkezés: ide kattintva.

2. Állapotgépes kód vizsgálata

Alább az előadás LY-számlálós feladatának megoldását látod.

#include <stdio.h>

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

    int szaml = 0;
    LyAllapot all = alap;
    int c;
    while ((c=getchar()) != EOF) {
        switch (all) {
            case alap:
                if (c == 'l') all = l_volt;
                break;

        case l_volt:
            switch (c) {
                case 'l': all = ll_volt; break;
                case 'y': szaml += 1; all = alap; break;
                default: all = alap; break;
            }
            break;

        case ll_volt:
            switch (c) {
                case 'l': break;
                case 'y': szaml += 2; all = alap; break;
                default: all = alap; break;
            }
            break;
        }
    }

    printf("%d darab volt.\n", szaml);

    return 0;
}

Válaszolj 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. Megszámolja, a beolvasott szövegben hány ly volt. A hosszú lly-onokat duplának tekinti.
  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. „Hejesírásreform”

Rajzold meg az előző program állapotátmeneti és tevékenységeket tartalmazó táblázatát, vagy választásod szerint az állapotátmeneti gráfot!

Megoldás

Az „ly” számláló állapot- és tevékenységtáblája
lyegyéb
alap→l_volt--
l_volt→ll_voltsz+=1, →alap→alap
ll_volt-sz+=2, →alap→alap

Rajzolj egy új táblázatot, amelyben teljes egészében módosítod a tevékenységeket. Az új program feladata nem az ly-ok számlálása, hanem egy „hejesírásreform” végrehajtása. Ennek a beolvasott szöveget majdnem változatlanul kell kiírnia a kimenetre – azzal a különbséggel, hogy a beolvasott ly-ok helyett j-t, a beolvasott lly-ok helyett jj-t kell kiírnia! Pl. lyuk→juk, gally→gajj, viszont majom→majom marad, és a kulcs, a hallgat szavak is változatlanok maradnak. (Ezek a példák fontos állapotátmeneteket és tevékenységeket tesztelnek.)

Megoldás

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

A kiírásokat itt jól meg kell gondolni. Alapállapotban mindent kiírunk, kivétel az l betűt, mert az lehet egy későbbi ly része. l_volt állapotban bejövő y esetén kiírjuk a j-t; viszont bejövő egyéb karakter esetén az előző l-t is ki kell írni, és a mostanit is (ilyen szó: kulcs). ll_volt esetén pedig, ha bármi más jön, akkor az előző ll-t is ki kell írni (ilyen szó: hallgat).

#include <stdio.h>

int main(void) {
    enum allapot {
        alap,
        l_volt,
        ll_volt
    } all;
    int c;          /* ennek kell intnek lennie! */

    all = alap;
    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;
}

4. Átirányítás fájlból, átirányítás fájlba

Emlékezz vissza a félév elején tanultakra: a programok parancssorból történő indításáról, a bemenet és kimenet átirányításáról volt szó.

  • Keresd meg a lefordított programod (pl. hejesiras.exe).
  • Indítsd el. Gépelj be neki egy szöveget! Próbáld ki, hogy itt is fájl vége jelet adsz a programnak.
  • Irányítsd a kimenetet egy fájlba a > operátor.
  • Hozz létre egy szövegfájlt, ments el bele valamilyen szöveget. Írd ki a képernyőre a fájlt, megreformált „hejesírással”, tehát irányítsd át a bemenetet a < operátorral.
  • Próbáld ki a bemenet és a kimenet egyidejű átirányítását is!

Megoldás

hejesiras > output.txt
hejesiras < input.txt

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 „hell”, é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ő (!) fájlra). Ezt úgy tudjuk kezelni, ha az állapotgép ciklusa után megvizsgáljuk az állapotváltozót. Az l_volt és a ll_volt állapotok azt jelentik, hogy a fájl l/ll karakter(ek)re végződött, lezáró újsor nélkül. Ezeket kiírhatjuk az állapotgép ciklusából kilépés után:

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

5. Lyuk

Fejleszd tovább a programot! „Tanítsd meg” az állapotgépednek, hogy kezelje helyesen a mondatot kezdő, nagybetűs L karaktert! Rajzold meg az új állapotátmeneti táblázatot!

Hány új állapot kell ehhez? Működik helyesen a programod, ha azt írod bemenetként, Levél? Vajon kell-e számolnod azzal, hogy mondat elejére két j-t kell írnod?

Megoldás

#include <stdio.h>

int main(void) {
    enum allapot {
        alap,
        l_volt,
        ll_volt,
        L_volt,
    } all;
    int c;          /* ennek kell intnek lennie! */

    all = alap;
    while ((c=getchar())!=EOF) {
        switch (all) {
            case alap:
                switch (c) {
                    case 'l': all = l_volt; break;
                    case 'L': all = L_volt; break;
                    default: putchar(c); break;
                }
                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;
            case L_volt:        /* az új állapot */
                switch (c) {
                    case 'l':
                        /* ez lehetetlen... szó elején nem lehet hosszú msh. */
                        /* Ugyanezért nem lehet Lly sem, amiből amúgy Jj lenne. */
                        /* valami azért történjen - hagyjuk változatlanul */
                        printf("Ll"); all = alap; break;
                    case 'y': putchar('J'); all = alap; break;
                    default: printf("L%c", c); all=alap; break;
                }
                break;
        }
    }

    return 0;
}

6. További feladatok

Ha elkészültél, folytasd a feladatgyűjtemény kapcsolódó feladataival!