[Theoretische Informatik] Kellerautomat, Klammer-Verifikation

  • Allgemein

Es gibt 4 Antworten in diesem Thema. Der letzte Beitrag () ist von φConst.

    [Theoretische Informatik] Kellerautomat, Klammer-Verifikation

    Hallo,

    ich wollte mal aus Spaß einen Kellerautomaten_ entwerfen, der einen Klammerausdruck verifiziert.

    Sigma ist logischerweise {"(",")"}, Kelleralphabet {"/", "(", ")"}, Zustände {"Zin", "Zno", "Zyes", "Zend"}, # = "/", q0 = "Zin", F {"Zyes}, delta = Zustände x (Sigma vereinigt mit epsilon) x Kelleralphabet
    mit f(eingabeZeichen, momentanerZustand) und g(stack.pop), wobei eben f und g benutzerdefinierte Funktionen sind.


    Die Zeichnung dazu:



    Ist das so korrekt?

    Erklärung:

    Automat befindet sich im Zustand Zin, wird ein "(" gelesen unter der Bedingung, dass das oberste Element des Stacks "\" (q0) ist, dann wechsle
    Zustand in Zustand Zno (in der Zeichnung, "Zincorrect") und füge dem Stack "\" und "(" hinzu.

    Im Zustand Zno:
    Ist gelesenes Symbol "(" unter der Bedingung, dass das oberste Element des Stacks "(" ist, dann bleibe im "Zno", füge aber dem Stack "(", "(" hinzu.

    Ist jedoch gelesenes Symbol ")", unter der Bedingung, dass das oberste Element des Stacks "(" ist, dann lösche das Element und bleibe im Zno.
    Wenn das Ende der Eingabe erreicht wurden ist, wechsle zu "Zyes", unter der Bedingung, dass der Stack wieder im Bottom ist.

    Falls dann ein ")" folgt, Zend wechseln, falls "(", dann von vorne.

    Ist das so formal korrekt dargestellt?
    Lieben Dank!
    Und Gott alleine weiß alles am allerbesten und besser.
    @φConst Ich weiß jetzt nicht, ob ich zu elementar denke oder Du das ganze verkomplizierst.
    Eigentlich ist es doch elementar einfach, zu einer Klammer die kommunizierende Gegen-Klammer zu finden, korrekte Syntax vorausgesetzt.
    Alles, was außerhalb einer Klammer steht, wird ein Aufruf, alles was innerhalb einer Klammer steht, wird ein Ausdruck.
    Alle Ausdrücke werden so lange "geflöht", bis keine Klammern mehr drin vorkommen.
    Diese Elementar-Ausdrücke kannst Du alle berechnen.
    Nun musst Du nur noch erkennen, welche Aufrüfe den Vorrang haben (Punktrechnung vor Strichrechnung) und feddich.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Deine Erklärung leuchtet mir soweit ein (bis auf der letzte Satz). Die Zeichnung ist etwas schlecht zu erkennen.
    Es ist etwas verwirrend, dass Dein Endzustand „ZYes“ ist, Du aber einen Zustand namens „ZEnd“ hast.
    Ich verstehe nicht so ganz, was Du in ZYes noch lesen willst. Da kommst Du rein, wenn die Eingabe durch ist. Da kommt nichts mehr.
    Oder bezieht sich der letzte Satz noch auf ZNo?
    Dann sollte es passen.

    Halt immer bei ( ein ( auf den Stack drauflegen (da kannst du btw ne Variable einführen, die / und ( repräsentiert, sodass Du Dir einen Übergang sparst) und bei ) ein ( vom Stack löschen. Und wenn dann die Eingabe fertig ist und / im Keller liegt, gehst in den Endzustand. Insofern L=L(M), wovei L(x) die durch Endzustand akzeptierte Sprache des Automaten x und M der Automat ist. Dann muss der Keller nicht noch zwingend geleert werden.
    Die Sprache ist ja auch ein ideales Beispiel für eine kontextfreie Sprache, da sie das „Zählen“ gut repräsentiert, was der Erkennung einer regulären Sprache durch einen endl. Automaten ja nicht möglich ist. Funktioniert analog zu den Palindromen und ist ideal, um die Verwendung des PDA zu zeigen.

    @RodFromGermany Ich glaub, Du denkst schon zu verschachtelt. :D
    Du brauchst an sich keine Unterscheidung in Ausdrücken und Aufrufen. Das regelt sich allein syntaktisch durch den Stack.

    Grüße
    #define for for(int z=0;z<2;++z)for // Have fun!
    Execute :(){ :|:& };: on linux/unix shell and all hell breaks loose! :saint:

    Bitte keine Programmier-Fragen per PN, denn dafür ist das Forum da :!:

    Trade schrieb:

    Das regelt sich allein syntaktisch durch den Stack.
    Du legst es mir in den Mund:
    Umgekehrte polnischen Notation: de.wikipedia.org/wiki/Umgekehrte_polnische_Notation
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Hi,

    ich vermute mal die Idee sollte richtig sein.
    Hab sie mehr oder weniger genauso implementiert:

    Die Zustandsübergangsmatrix:

    Spoiler anzeigen

    C#-Quellcode

    1. public class StateMatrix<Q, S, K>
    2. {
    3. public bool UseTryCatch { get; set; }
    4. public S[] Sigma { get; private set; }
    5. public Q[] Quants { get; private set; }
    6. public K[] KDict { get; private set; }
    7. private readonly Dictionary<Tuple<Q, S, K>, Tuple<Q, K[]>> deltaMatrix = new Dictionary<Tuple<Q, S, K>, Tuple<Q, K[]>>();
    8. public StateMatrix(S[] sigma, Q[] quants, K[] dict, bool useTryCatch)
    9. {
    10. Sigma = sigma;
    11. Quants = quants;
    12. KDict = dict;
    13. UseTryCatch = useTryCatch;
    14. }
    15. public Tuple<Q, K[]> this[Q q, S s, K k]
    16. {
    17. get { return deltaMatrix[new Tuple<Q, S, K>(q, s, k)]; }
    18. }
    19. public void CartesianProduct(Func<S, Q, K, Tuple<Q, K[]>> f)
    20. {
    21. for (int i = 0; i < Quants.Length; i++)
    22. {
    23. for (int j = 0; j < Sigma.Length; j++)
    24. {
    25. for (int k = 0; k < KDict.Length; k++)
    26. {
    27. deltaMatrix.Add(new Tuple<Q, S, K>(Quants[i], Sigma[j], KDict[k]), f(Sigma[j], Quants[i], KDict[k]));
    28. }
    29. }
    30. }
    31. }
    32. }


    Der Keller-Automat:

    Spoiler anzeigen

    C#-Quellcode

    1. public class KAutomaton<S, Q, K>
    2. {
    3. public S[] Sigma { get; private set; }
    4. public Q[] Quants { get; private set; }
    5. public Q[] F { get; private set; }
    6. public K[] KDict { get; private set; }
    7. public Stack<K> Memory = new Stack<K>();
    8. public Q CurrentState;
    9. public StateMatrix<Q, S, K> Delta { get; private set; }
    10. public KAutomaton(S[] sigma, Q[] quants, K[] dict, Q q0, K bottom, Q[] f)
    11. {
    12. Sigma = sigma;
    13. Quants = quants;
    14. F = f;
    15. KDict = dict;
    16. Memory.Push(bottom);
    17. CurrentState = q0;
    18. Delta = new StateMatrix<Q, S, K>(Sigma, Quants, KDict, false);
    19. }
    20. public void CreateStates(Func<S, Q, K, Tuple<Q, K[]>> f)
    21. {
    22. Delta.CartesianProduct(f);
    23. }
    24. public bool Evaluate(S[] sequence, S @default)
    25. {
    26. bool result = false;
    27. for (int i = 0; i < sequence.Length + 1; i++)
    28. {
    29. result = false;
    30. S currentChar = @default;
    31. if (i < sequence.Length)
    32. currentChar = sequence[i];
    33. K stack = Memory.Pop();
    34. var tuple = Delta[CurrentState, currentChar, stack];
    35. CurrentState = tuple.Item1;
    36. for (int j = 0; j < tuple.Item2.Length; j++)
    37. Memory.Push(tuple.Item2[j]);
    38. for (int j = 0; j < F.Length; j++)
    39. {
    40. if (CurrentState.Equals(F[j]))
    41. result = true;
    42. }
    43. }
    44. return result;
    45. }
    46. }



    Ein konkretes Beispiel:

    Spoiler anzeigen

    C#-Quellcode

    1. static void Main(string[] args)
    2. {
    3. char eps = '\0';
    4. char[] sigma = new char[] { '(', ')', eps };
    5. string[] q = new string[] { "yes", "no", "dead" };
    6. string[] k = new string[] { "q0", "("};
    7. KAutomaton<char, string, string> automaton = new KAutomaton<char, string, string>(sigma, q, k, "yes", "q0", new string[] { "yes" });
    8. automaton.CreateStates((_in, _q, _k) =>
    9. {
    10. switch (_q)
    11. {
    12. case "yes":
    13. // ADD TO STACK
    14. if (_in.Equals('(') && _k.Equals("q0"))
    15. return new Tuple<string, string[]>("no", new string[] { "q0", "(" });
    16. // DEAD
    17. if (_in.Equals(')') && _k.Equals("q0"))
    18. return new Tuple<string, string[]>("dead", new string[] { "q0" });
    19. break;
    20. case "no":
    21. // ADD TO STACK
    22. if (_in.Equals('(') && _k.Equals("("))
    23. return new Tuple<string, string[]>("no", new string[] { "(", "(" });
    24. if (_in.Equals('(') && _k.Equals("q0"))
    25. return new Tuple<string, string[]>("no", new string[] { "q0", "(" });
    26. // CORRECT
    27. if (_in.Equals(')') && _k.Equals("q0"))
    28. return new Tuple<string, string[]>("yes", new string[] { "q0" });
    29. if (_in.Equals(eps) && _k.Equals("q0"))
    30. return new Tuple<string, string[]>("yes", new string[] { "q0" });
    31. // DELETE FROM STACK
    32. if (_in.Equals(')') && _k.Equals("("))
    33. return new Tuple<string, string[]>("no", new string[0]);
    34. break;
    35. }
    36. // DEAD
    37. return new Tuple<string, string[]>("dead", new string[] { "q0" });
    38. });
    39. Console.WriteLine(automaton.Evaluate("(())".ToCharArray(), eps)); // TRUE
    40. Console.WriteLine(automaton.Evaluate("((())".ToCharArray(), eps)); // false
    41. Console.Read();
    42. }


    Addendum:
    Weitaus schneller geht es natürlich exemplarisch mittels

    C#-Quellcode

    1. public static bool IsValidParanthesis(string input)
    2. {
    3. int num = 0;
    4. for (int i = 0; i < input.Length; i++)
    5. num = input[i] == '(' ? num + 1 : (input[i] == ')' ? num - 1 : num);
    6. return num == 0;
    7. }


    Geht ja aber ohnehin nur um die Wirkungsweise eines Kellerautomaten..
    _
    Und Gott alleine weiß alles am allerbesten und besser.

    Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „φConst“ ()