Kellerautomat. Mehrere Zeichen.



  • Darf ich in einem Kellerautomaten, mehrere Zeichen gleichzeitig einlesen. Oder aus dem Speicher auslesen?

    Wie würde man sonst solche eine Spiegelung hinkriegen?
    aabc|ccba



  • eddi0815 schrieb:

    Darf ich in einem Kellerautomaten, mehrere Zeichen gleichzeitig einlesen. Oder aus dem Speicher auslesen?

    Wie soll das denn gehen? Also es kommt natürlich auf die Definition an. Die, die ich kenne erlaubt nur ein Zeichen einzulesen und wieder auszugeben.

    eddi0815 schrieb:

    Wie würde man sonst solche eine Spiegelung hinkriegen?
    aabc|ccba

    Mit einem deterministischen Kellerautomaten geht das nicht, AFAIK. Dafür brauchst du einen nicht-deterministischen Kellerautomat.

    Dein Beispiel verstehe ich übrigens nicht. Soll das ein Beispiel dafür sein, was der Automat ablehnen soll?

    Oder hast du einen Automat, der eine Ausgabe erzeugt?



  • ich vermute, dass deine Sprache nicht mehr kontextfrei sondern kontextsensitiv ist. Von daher geht das gar nicht, solange die Worte nicht eine maximale Länge haben (und dann ist die Sprache sofort regulär)



  • Wörter der Sprache

    Gehören dazu:
    1) bcaacaa|accaccb#bcc|ccccb± 
    2) bcbb|bbccb#|±
    3) aac|cca± 
    4) |#|± 
    5) caab|bacc#caa|acc±; 
    6) |#bcbb|bbccb#|#aaaaaa|aaa#|±; 
    
    Gehören nicht dazu:
    7) bcac|caccb#aa|a±
    8) b|a±
    9) caab|bacc#±
    10) bcac|ccacb#a|b±
    

    Grammatik

    S -> A±
    A -> B#B   
    A -> B
    B -> aaBa
    B -> bBb
    B -> cBcc
    B -> |
    

    Folgende Bedingungen:
    ± schließt das Wort ab und kommt nur einmal vor.
    # trennt ein Teilwort, dann beginnt ein Neues
    | trennt ein Teilwort und die Buchstaben werden gespiegelt.
    links vom | kommen die a,b, und c beleibig vor. a muß aber doppelt stehen > aa
    rechts vom | kommen a,b und c beliebig vor. cc muß aber doppelt stehen.

    Daraus soll ich jetzt ein determistischen Kellerautomaten bauen.
    Die Frage die habe bezieht sich auf die Spiegelung bei dem |.
    Links steht aa rechts a.
    Links steht c rechts cc.
    Wenn ich immer nur ein Zeichen einlesen kann, woher weiß der Automat, daß er bei einem c zei cc in den Speicher schreiben muß. Und bei zwei aa nur ein a in den Speicher.

    Grüße



  • eddi0815 schrieb:

    Links steht aa rechts a.
    Links steht c rechts cc.
    Wenn ich immer nur ein Zeichen einlesen kann, woher weiß der Automat, daß er bei einem c zei cc in den Speicher schreiben muß. Und bei zwei aa nur ein a in den Speicher.

    Indem du mehrere Zustände verwendest. Wenn du links ein "a" gelesen hast, dann bedeutet dass, dass mindestens ein zweites Kommt.

    Also:

    a gelesen in Zustand q_1 -> Packe a auf den Keller und wechsele in Zustand q_2
    ...
    a gelesen in Zustand q_2 -> Wechsel in Zustand q_1

    Analog für die Zwei "c"s. Übrigens: Der DKA ist nur möglich, da du ein Trennzeichen hast. Ohne Trennzeichen gehts nur mit einem NKA.



  • Hm...? Ich habe mal gelernt, dass Deterministische und Nicht-deterministische Automaten gleichmächtig sind. Nur ist die Anzahl der Zustände beim letzteren wesentlich geringer.



  • Ad aCTa schrieb:

    Hm...? Ich habe mal gelernt, dass Deterministische und Nicht-deterministische Automaten gleichmächtig sind. Nur ist die Anzahl der Zustände beim letzteren wesentlich geringer.

    Das gilt nur für (nicht-)deterministische endliche Automaten. Bei Kellerautomaten gilt dies nicht!



  • Könnte dieser Automat für die o.g. Grammatik hinhauen?
    E = das leere Wort.
    ± = Schlussymbol

    S = {s0, s1, s2, s3, s4 s5,s6}
    T = {a, b, c. #, |, ±}
    K = {a, b, c. #, |, ±, E}
    E = {s6}
    
    (s1, ±, E)	=	{(s6, E)}
    (s1, # ,E)	=	{(s1, E)}
    (s1, a, a)	=	{(s2, a)}
    (s1, b, b)	=	{(s1, b)}
    (s1, c, c)	=	{(s3, c)}
    (s1, | ,E)	=	{(s4, E)}
    (s2, a, E)	=	{(s1, E)}
    (s3, c, c)	=	{(s1, c)}
    (s4, a, E)	=	{(s4, E)}
    (s4, b, E)	=	{(s4, E)}
    (s4, c, E)	=	{(s5, E)}
    (s5, c, E)	=	{(s1, E)}
    

Log in to reply