PROGRAM NFA(INPUT,OUTPUT);                                  
(*3. AUFGABENBLATT ZU INFORMATIK IV                       *)
(*EINGABEFORMAT:                                          *)
(* VON MIT NACH (FUER ALLE KANTEN)                        *)
(*$             (ENDE MARKIERUNG)                         *)
CONST ENDE="$";                                             
TYPE TEINGABE=CHAR;            (*0..9,A..Z*)                
     TKNOTENREF=^TKNOTEN;                                   
     TKANTENREF=^TKANTE;                                    
     TKNOTEN=RECORD                                         
              NUMMER:INTEGER;  (*NEGATIV, FALLS ENDZUSTAND*)
              ISTMARKIERT:BOOLEAN;                          
              KANTENLISTE:TKANTENREF;                       
              NEXT:TKNOTENREF; (*BILDET LISTE ALLER KNOTEN*)
             END;                                           
     TKANTE =RECORD                                         
              MARKIERUNG:TEINGABE;                          
              TAU:TKNOTENREF;  (*ENDE DER KANTE           *)
              NEXT:TKANTENREF  (*BILDET LISTE ALLER KANTEN*)
             END;              (*DIESES KNOTENS           *)
                                                            
VAR KNOTENLISTE,Q0:TKNOTENREF;                              
    W:ARRAY[1..100]OF TEINGABE;                             
    I:INTEGER;                                              
                                                            
 PROCEDURE GRAPHEINLESEN;                                   
 (*BILDE KNOTENLISTE. Q0 ZEIGT AUF 1. ZUSTAND*)             
  VAR CH:CHAR;ISTERSTER:BOOLEAN;                            
      EIN:TEXT;                                             
      VON,NACH:INTEGER;                                     
      MIT:TEINGABE;                                         
      V,N:TKNOTENREF;                                       
      KANTE:TKANTENREF;                                     
                                                            
  FUNCTION SUCHEKNOTEN(N:INTEGER):TKNOTENREF;               
  (*NIL, FALLS NICHT GEFUNDEN*)                             
   VAR Q:TKNOTENREF;                                        
  BEGIN                                                     
   Q:=KNOTENLISTE;SUCHEKNOTEN:=NIL;                         
   WHILE Q<>NIL DO                                          
      IF Q^.NUMMER=N THEN                                   
       BEGIN SUCHEKNOTEN:=Q;Q:=NIL END                      
      ELSE Q:=Q^.NEXT                                       
  END;(*SUCHEKNOTEN*)                                       
                                                            
  FUNCTION NEUERKNOTEN(N:INTEGER):TKNOTENREF;               
  (*EINFUEGEN AM ANFANG VON KNOTENLISTE*)                   
   VAR Q:TKNOTENREF;                                        
  BEGIN                                                     
   NEW(Q);                                                  
   WITH Q^ DO                                               
    BEGIN                                                   
     NUMMER:=N;ISTMARKIERT:=FALSE;                          
     KANTENLISTE:=NIL;NEXT:=KNOTENLISTE                     
    END;                                                    
   KNOTENLISTE:=Q;                                          
   NEUERKNOTEN:=Q                                           
  END;(*NEUERKNOTEN*)                                       
                                                            
 BEGIN  (*EINLESEN DES GRAPHEN:*)                           
  KNOTENLISTE:=NIL;                                         
  OPEN(EIN,8,3,"GRAPH,S,R");                                
  ISTERSTER:=TRUE;                                          
  REPEAT                                                    
    READ(EIN,VON);                                          
    REPEAT READ(EIN,MIT) UNTIL MIT<>" ";                    
    READ(EIN,NACH);                                         
    WRITELN(VON,MIT,NACH);                                  
    V:=SUCHEKNOTEN(VON);                                    
    IF V=NIL THEN V:=NEUERKNOTEN(VON);                      
    N:=SUCHEKNOTEN(NACH);                                   
    IF N=NIL THEN N:=NEUERKNOTEN(NACH);                     
    (*BILDE KANTE (VON,MIT,NACH) *)                         
    NEW(KANTE);KANTE^.MARKIERUNG:=MIT;KANTE^.TAU:=N;        
    KANTE^.NEXT:=V^.KANTENLISTE;V^.KANTENLISTE:=KANTE;      
    IF ISTERSTER THEN BEGIN ISTERSTER:=FALSE;Q0:=V END;     
   READ(EIN,CH)                                             
  UNTIL CH=ENDE;                                            
  CLOSE(EIN);                                               
 END;(*EINLESEN*)                                           
                                                            
 FUNCTION ISTLEER(Q:TKNOTENREF):BOOLEAN;                    
  VAR LEER:BOOLEAN;NACHF:TKANTENREF;                        
 BEGIN                                                      
  Q^.ISTMARKIERT:=TRUE;                                     
  LEER:=Q^.NUMMER>=0;                                       
  NACHF:=Q^.KANTENLISTE;                                    
  WHILE LEER AND(NACHF<>NIL) DO                             
  BEGIN                                                     
     IF NOT NACHF^.TAU^.ISTMARKIERT THEN                    
        LEER:=ISTLEER(NACHF^.TAU);                          
     NACHF:=NACHF^.NEXT                                     
  END;                                                      
  ISTLEER:=LEER                                             
 END;(*ISTLEER*)                                            
                                                            
 FUNCTION ERKANNT(Q:TKNOTENREF;I:INTEGER):BOOLEAN;          
 (*PRUEFE, OB ENDZUSTAND MIT WORT W[I] ERREICHT WIRD*)      
  VAR OK:BOOLEAN;NACHF:TKANTENREF;                          
 BEGIN                                                      
  IF W[I]=ENDE THEN ERKANNT:=Q^.NUMMER<0 ELSE               
   BEGIN                                                    
     OK:=FALSE;NACHF:=Q^.KANTENLISTE;                       
     WHILE NOT OK AND (NACHF<>NIL) DO                       
     BEGIN                                                  
        IF NACHF^.MARKIERUNG=W[I] THEN                      
            OK:=ERKANNT(NACHF^.TAU,I+1);                    
        NACHF:=NACHF^.NEXT                                  
     END;                                                   
    ERKANNT:=OK                                             
   END                                                      
 END;(*ERKANNT*)                                            
                                                            
BEGIN                                                       
 GRAPHEINLESEN;                                             
 (*PRUEFE AUF LEER. ALLE MARKIERUNGEN SIND RUECKGESETZT!  *)
 WRITE("DER NFA ERREICHT ");                                
 IF ISTLEER(Q0) THEN WRITE("NIE ");                         
 WRITELN("EINEN ENDZUSTAND");                               
 REPEAT                                                     
  I:=0;                                                     
  REPEAT                                                    
   I:=I+1;READ(W[I]);                                       
  UNTIL W[I]=ENDE;                                          
  WRITELN;WRITE("DAS WORT IST ");                           
  IF NOT ERKANNT(Q0,1) THEN WRITE("NICHT ");                
  WRITELN("IN DER SPRACHE");                                
 UNTIL FALSE;                                               
END.