Zadání úlohy č. 1

[test.txt] [Automat.class] [Uloha1.java] [Soubory pro C#]
[Řešení v Javě] [Řešení v C#]

Implementace konečného automatu

Vytvořte program, který simuluje činnost konečného automatu. Konečný automat je pětice definovaná množinou stavů, vstupních symbolů, přechodovou funkcí, počátečním stavem a množinou koncových stavů. Stavy automatu budou označeny nezápornými celými čísly počínaje nulou, počátečním stavem bude vždy stav 0. Vstupními symboly budou tisknutelné ASCII znaky (bez mezery). Program čte vstupní data ze standardního vstupu a výsledky zapisuje na standardní výstup.

Specifikace vstupu:

Vstup se skládá ze Z zadání. První řádek vstupu obsahuje právě jedno celé kladné číslo Z. Dále následují jednotlivá zadání. Každé zadání je tvořeno následujícími údaji:

• První řádek obsahuje kladné celé číslo označující počet stavů konečného automatu.
• Druhý řádek obsahuje posloupnost znaků (bez oddělovačů) reprezentujících vstupní symboly.
• Třetí řádek obsahuje kladné celé číslo označující počet koncových stavů a na dalším řádku je seznam čísel koncových stavů oddělených od sebe mezerou.
• Další řádek obsahuje kladné celé číslo označující počet položek tabulky přechodové funkce; každá položka je tvořena číslem výchozího stavu, vstupním symbolem a číslem cílového stavu, hodnoty jsou odděleny mezerou.

Za zadáním automatu následují testovací řetězce. První řádek obsahuje počet řetězců, další řádky pak obsahují postupně jednotlivé řetězce, pro které má být činnost automatu testována.

Specifikace výstupu:

Pro každé zadání testovacího řetězce vypíše program na standardní výstup text ANO, je-li řetězec automatem přijat, resp. NE, pokud řetězec přijat není.

Příklad:

Automat na obrázku přijímá všechny řetězce znaků a, b, ve kterých je lichý počet znaků b. Odpovídající zadání je následující:

1              počet příkladů = 1
2              stavy = {0,1}
ab             vstupní symboly = {a,b}
1              počet koncových stavů = 1
1              koncové stavy = {1}
4              přechodová funkce (4 položky):
0 a 0             f(0, a) = 0
0 b 1             f(0, b) = 1
1 b 0             f(1, b) = 0
1 a 1             f(1, a) = 1
2              testovací příklady (2 příklady):
aaabaabaaba       ANO
baba              NE

ANO
NE

Poznámky:

Při čtení vstupních dat předpokládejte, že zadání neobsahuje žádné formální ani věcné chyby. Uvedená čísla stavů jsou např. vždy menší než zadaný počet stavů, symboly v zadání přechodové funkce a testovacích řetězcích jsou vždy prvky zadané množiny vstupních symbolů.

Program v jazyce Java bude mít přibližně následující strukturu:

import java.io.*;
import java.util.StringTokenizer;

public class Automat {
   static int readNumber(BufferedReader inp) throws IOException
   {
      return Integer.parseInt(inp.readLine().trim());
   }

   public static void main(String[] args) throws IOException
   {
      BufferedReader inp = new BufferedReader(
                              new InputStreamReader(System.in));
      int pocet = readNumber(inp);
      for(int i = 0; i < pocet; i++) {
         priklad(inp);
      }
   }

   static void priklad(BufferedReader inp) throws IOException
   {
      ...
      // příklad čtení seznamu čísel na jednom řádku
      int n = readNumber(inp);
      StringTokenizer st = new StringTokenizer(inp.readLine());
      for(int i = 0; i < n; i++) {
         int x = Integer.parseInt(st.nextToken());
         ...
      }
      ...
   }
}