/** * TM_Klammerausdruecke simuliert eine Turingmaschine, welche Klammerausdruecke mit passenden oeffnenden * und schliessenden Klammern erkennt, was ein endlicher Automat nicht kann. * Die Maschine verwendet das Zeichen "K", um (a) rechts hinter der Eingabe die Anzahl der oeffnenden Klammern zu * notieren und (b) die zuletzt bearbeitete Stelle zu markieren * * @author MB * @version SEP 2020 */ public class Klammerausdruecke extends TM { /** * Constructor for objects of class TM_Nachfolgerfunktion */ public Klammerausdruecke() { // initialise instance variables zustand = 0; band = new char[100]; index = 1; // Band startet links mit 'B'; Lesekopf steht am Anfang auf dem Feld rechts davon } @Override protected void bandInitialisieren(char[] eingabe){ // Band evtl. verlaengern if (eingabe.length > (band.length/2)){ band = new char[eingabe.length*3]; // maximale Verdoppelung, wenn der Ausdruck nur aus Klammern besteht } // eingabe auf das Band schreiben for (int i = 0; i < eingabe.length; i++){ if ((eingabe[i] == 'a') || (eingabe[i] == '(')){ band[i] = eingabe[i]; } else if ((eingabe[i] == ')') || (eingabe[i] == 'K')){ band[i] = eingabe[i]; } else { band[i] = 'B'; } } for (int i = eingabe.length; i < band.length; i++){ band[i] = 'B'; } } /** * @param ein - der Bandinhalt als String, beginnend mit einem "B" * Beispieleingabe: "Ba(aa(a))((aa))" */ public void klammernpruefen(String ein){ char[] eingabe = new char[ein.length()]; for (int i = 0; i < ein.length(); i++){ eingabe[i] = ein.charAt(i); } if (eingabe[0] != 'B'){ System.err.println("Falsche Eingabe"); return; } int counter = 1; // Counter fuer die Arbeitsschritte zustand = 0; // Startzustand band = new char[100]; // dummy Startwert fuer die Laenge des Bandes index = 1; // Band startet links mit 'B'; Lesekopf steht am Anfang auf dem Feld rechts davon bandInitialisieren(eingabe); int neueBandlaenge = band.length; System.out.println("Bandlänge nach Initialisierung: " + neueBandlaenge); System.out.println(); int laenge = eingabe.length - 1; // initiales "B" zaehlt nicht int limit = laenge * 4 * laenge; // Schaetzwert fuer maximale Laufzeit bei Erfolg while (zustand != 13 && counter < limit){ // wenn der Endzustand nicht erreicht wird, Abbruch nach Limit System.out.print("Schritt " + counter + ":\t "); for (int j = 0; j < band.length; j++){ if (j == index){ System.out.print(" [" + band[j]); } else if (j == index+1){ System.out.print("] " + band[j]); } else{ System.out.print(" " + band[j]); } } System.out.println(); try { Thread.sleep(1000); uebergangsfunktion(); } catch (Exception e){ System.out.println(e.toString()); } counter++; // Zaehlen der Arbeitsschritte } if (zustand == 13){ // letzten Bandinhalt schreiben System.out.print("Schritt " + counter + ":\t "); for (int j = 0; j < band.length; j++){ if (j == index){ System.out.print(" [" + band[j]); } else if (j == index+1){ System.out.print("] " + band[j]); } else{ System.out.print(" " + band[j]); } } System.out.println(); System.out.println("" + (counter) + " Schritte benötigt."); } } protected void uebergangsfunktion(){ switch (zustand){ // Startzustand case 0: { switch(lesen()){ case '(':{ zustand = 1; schreiben('K'); // eine Klammer gefunden rechts(); // Schritt nach rechts break; } case 'a':{ zustand = 0; // "a" wird uebersprungen rechts(); break; } case 'B': { zustand = 9; // Ende der Eingabe erreicht rechts(); break; } case ')':{ zustand = 5; schreiben('K'); rechts(); break; } case 'K': { break; } } break; } // Zustand, der das Ende der Eingabe sucht case 1: { switch(lesen()){ case '(':{ zustand = 1; rechts(); // Schritt nach rechts break; } case 'a':{ zustand = 1; rechts(); break; } case 'B': { zustand = 2; rechts(); break; } case ')':{ zustand = 1; rechts(); break; } case 'K': { break; } } break; } // Zustand, der notiert, eine oeffnende Klammer gefunden zu haben case 2: { switch(lesen()){ case '(':{ break; } case 'a':{ break; } case 'B': { zustand = 3; schreiben('K'); links(); // Schritt nach links break; } case ')':{ break; } case 'K': { zustand = 2; rechts(); break; } } break; } // Zustand, der zurueck an das Ende der Eingabe faehrt case 3: { switch(lesen()){ case '(':{ break; } case 'a':{ break; } case 'B': { zustand = 4; links(); // Schritt nach links break; } case ')':{ break; } case 'K': { zustand = 3; links(); break; } } break; } // Zustand, der vom Ende der Eingabe zurueck zur weiteren Verarbeitung faehrt case 4: { switch(lesen()){ case '(':{ zustand = 4; links(); break; } case 'a':{ zustand = 4; links(); break; } case 'B': { break; } case ')':{ zustand = 4; links(); break; } case 'K': { zustand = 0; rechts(); break; } } break; } // Zustand, der an den Anfang der Klammernotizen faehrt case 5: { switch(lesen()){ case '(':{ zustand = 5; rechts(); // Schritt nach rechts break; } case 'a':{ zustand = 5; rechts(); break; } case 'B': { zustand = 6; rechts(); break; } case ')':{ zustand = 5; rechts(); break; } case 'K': { break; } } break; } // Zustand, der auf Klammernotizen testet, // um dann durch den uebernaechsten Zustand eine Klammer loeschen zu lassen case 6: { switch(lesen()){ case '(':{ break; } case 'a':{ break; } case 'B': { zustand = 6; // Fehler: eine oeffende Klammer zu wenig; vgl. Zustand 9 break; } case ')':{ break; } case 'K': { zustand = 7; rechts(); break; } } break; } // Zustand, der das Ende der Klammernotizen sucht und evtl. findet case 7: { switch(lesen()){ case '(':{ break; } case 'a':{ break; } case 'B': { zustand = 8; links(); // Schritt nach links break; } case ')':{ break; } case 'K': { zustand = 7; rechts(); break; } } break; } // Zustand, der genau ein Klammerzeichen loescht case 8: { switch(lesen()){ case '(':{ break; } case 'a':{ break; } case 'B': { break; } case ')':{ break; } case 'K': { zustand = 3; schreiben('B'); // eine Klammernotiz wird geloescht: passende schliessende Klammer gefunden links(); break; } } break; } // Zustand, der abschliessend testet, dass keine Klammernotizen mehr vorhanden sind case 9: { switch(lesen()){ case '(':{ break; } case 'a':{ break; } case 'B': { zustand = 10; break; } case ')':{ break; } case 'K': { zustand = 9; // Fehler: eine oeffende Klammer zu viel; vgl. Zustand 6 break; } } break; } // Zurueckfahren an das Ende der Eingabe case 10: { switch(lesen()){ case 'K': case 'a': { schreiben('B'); links(); zustand = 11; break; } case 'B': { // letztes 'B' ueberspringen links(); zustand = 10; break; } } break; } case 11: { switch(lesen()){ case 'K': case 'a': { schreiben('B'); links(); zustand = 11; break; } case 'B': { rechts(); zustand = 12; break; } } break; } case 12: { // Akzeptanzzustand mit Ausgabe '1' switch(lesen()){ case 'B': { schreiben('1'); // akzeptiert zustand = 13; break; } } break; } } } }