Zum Inhalt springen

Rabin-Automat

aus Wikipedia, der freien Enzyklopädie

Der Rabin-Automat ist eine spezielle Form des ω-Automaten. Sie sind benannt nach ihrem Erfinder Michael O. Rabin<ref name=":0" />, der damit 1969 erstmals endliche Automaten auf unendliche Wörter verallgemeinerte<ref>{{#invoke:Vorlage:Literatur|f}}</ref><ref name=":0" />.

Rabin-Automaten zur Worterkennung

Nichtdeterministischer Rabin-Automat zur Worterkennung

Ein nichtdeterministischer Rabin-Automat (NRA) ist ein 5-Tupel <math>\mathcal{A} = \left(Q,\Sigma,\Delta,I,\mathcal{R}\right)</math> wobei gilt:

  • <math>Q</math> ist eine endliche Menge von Zuständen, die Zustandsmenge,
  • <math>\Sigma</math> ist eine endliche Menge von Symbolen, das Eingabealphabet,
  • <math>\Delta</math> ist die Übergangsrelation mit <math>\Delta \subseteq Q \times \Sigma \times Q</math>,
  • <math>I</math> ist eine endliche Menge von Zuständen mit <math>I \subseteq Q</math>, die Startzustandsmenge,
  • <math>\mathcal{R} \subseteq 2^Q \times 2^Q</math> ist eine Familie von Paaren von Zustandsmengen.

Deterministischer Rabin-Automat zur Worterkennung

Ein deterministischer Rabin-Automat (DRA) ist ein 5-Tupel <math>\mathcal{A} = \left(Q,\Sigma,\delta,q_0,\mathcal{R}\right)</math> wobei gilt:

  • <math>Q</math> ist eine endliche Menge von Zuständen, die Zustandsmenge,
  • <math>\Sigma</math> ist eine endliche Menge von Symbolen, das Eingabealphabet,
  • <math>\delta</math> ist die Übergangsfunktion mit <math>\delta\colon Q \times \Sigma \rightarrow Q</math>,
  • <math>q_0</math> ist der Startzustand mit <math>q_0 \in Q</math>,
  • <math>\mathcal{R} \subseteq 2^Q \times 2^Q</math> ist eine Familie von Paaren von Zustandsmengen.

Die Mächtigkeit von <math>\mathcal{R}</math> wird als Index des Automaten bezeichnet.<ref name=":0">{{#invoke:Vorlage:Literatur|f}}</ref>

Akzeptanzverhalten

Ein unendliches Wort <math>w=a_1a_2 \ldots</math> wird vom deterministischen Rabin-Automaten <math>\mathcal{A}</math> akzeptiert genau dann, wenn es für den zugehörigen unendlichen Pfad <math>\pi = q_0 \; \xrightarrow{a_1} \; q_1 \; \xrightarrow{a_2} \; q_2 \; \ldots</math> ein Paar <math>(L, U) \in \mathcal{R}</math> gibt mit

  • <math>\operatorname{Inf}(\pi) \cap L = \emptyset</math>, d. h. alle Zustände aus <math>L</math> werden nur endlich oft besucht, und
  • <math>\operatorname{Inf}(\pi) \cap U \neq \emptyset</math>, d. h. mindestens ein Zustand aus <math>U</math> wird unendlich oft besucht.

Eine Definition mit umgekehrter Bedeutung des Paars <math>(L,U)</math> ist ebenso möglich.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

Verhältnis zu Büchi-, Streett- und Muller-Automaten

Das Akzeptanzverhalten eines nichtdeterministischen Rabin-Automaten (NRA) ist allgemeiner als eines nichtdeterministischen Büchi-Automaten (NBA), daher gilt:

  • Für jeden NBA der Größe n gibt es einen äquivalenten NRA mit Index 1 und gleicher Größe n.<ref name=":0" />

Durch verallgemeinerte Potzenautomatenkonstruktion lässt sich zeigen, dass: 

          | )
          | {{#if:{{#ifeq:de|de||{{#if:de|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://home.in.tum.de/~gufler/files/afsb.pdf%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://home.in.tum.de/~gufler/files/afsb.pdf}}%7C%7C}}}}{{#if:Automaten, formale Sprachen und Berechenbarkeit|{{#if:{{#invoke:WLink|isValidLinktext|1=Automaten, formale Sprachen und Berechenbarkeit|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2017-02-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2017-02-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2017-02-03 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:648685||(?)}}}}}}{{#if: 2017-02-03|;}}}}{{#if: 2017-02-03| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2017-02-03 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2017-02-03|class=Zitationswartung}} }} {{#invoke:DateTime|format|2017-02-03|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:de|de||{{#if:de|1}}}}|{{#if:{{#if: 2017-02-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if:PDF | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|de|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2017-02-03 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}de|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if: 

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}} 

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch: 

   |0|=Vorlage:Toter Link/Core{{#if: http://home.in.tum.de/~gufler/files/afsb.pdf
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://home.in.tum.de/~gufler/files/afsb.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|http://home.in.tum.de/~gufler/files/afsb.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://home.in.tum.de/~gufler/files/afsb.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://home.in.tum.de/~gufler/files/afsb.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|http://home.in.tum.de/~gufler/files/afsb.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://home.in.tum.de/~gufler/files/afsb.pdf }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://home.in.tum.de/~gufler/files/afsb.pdf
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://home.in.tum.de/~gufler/files/afsb.pdf
      | {{#if:{{#invoke:URLutil|isWebURL|http://home.in.tum.de/~gufler/files/afsb.pdf}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://home.in.tum.de/~gufler/files/afsb.pdf Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://home.in.tum.de/~gufler/files/afsb.pdf
       | {{#if:{{#invoke:URLutil|isWebURL|http://home.in.tum.de/~gufler/files/afsb.pdf}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://home.in.tum.de/~gufler/files/afsb.pdf }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}}{{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref> Eine Rabinbedingung lässt sich jedoch auch in eine Büchi-Bedingung umwandeln, es gilt:

  • Für jeden NRA der Größe n und vom Index k gibt es einen äquivalenten NBA mit höchstens <math>n \cdot (k+1)</math> Zuständen.<ref name=":0" />

Die Akzeptanzbedingung des Rabin-Automaten ist dual zur Akzeptanzbedingung des Streett-Automaten. Daher lassen sich Deterministische Rabin- und Streett-Automaten leicht ineinander komplementieren und es gilt:

  • Für jeden DRA <math>\mathcal{A}</math> der Größe n und vom Index k gibt es einen deterministischen Streett-Automaten <math>\overline\mathcal{A}</math> der Größe n und vom Index k dessen Sprache komplementär zur Sprache von <math>\mathcal{A}</math> ist: <math>L(\overline\mathcal{A})= \Sigma^\omega \setminus L(\mathcal{A})</math>.<ref name=":0" />

Des Weiteren gilt:

  • Jeder DRA ist zu einem deterministischen Muller-Automaten (DMA) äquivalent und umgekehrt.

Quellen und Weblinks

Einzelnachweise

<references />

en:Rabin automaton

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Rabin-Automat&oldid=648685“