(07) Kontextsensitive Sprachen, allgemeine Sprachen und Turingmaschinen 1/2 / Berechenbarkeit und Komplexität  1/2 Jürgen Branke. Yovisto Academic Video Search. Menge ... Turing Sprachen Grammatik Typ endlicher gilt Maschine Funktion Definition Bandinschrift Berechenbarkeit abzählbar Verfahren Universität Karlsruhe alan klass nichtdeterminist turing-maschin erkannt satz beweiside konfigurationsubergang konf schichtweis simulation determinist maschin endkonfiguration bemerk ndet-tm konfigurationsfolg akzepti wort abc bemerk schreiblesekopf zeich ubergeh definition nichtdeterminist turingmaschin turing-maschin tupel determinist abbild wort konfigurationenfolg endkonfiguration akzeptiert turing-berechenbar fragestell ide aufzahlbar meng definition surjektiv berechenbar funktion satz umkehr beispiel primzahl vorgelegt zahl endlich meng algorithmus kontextfrei grammat entscheidbar meng charakterist funktion true fals definition entscheidungsverfahr lemma algorithmus defini funktion wahl definition widerspruch text endlich lang beschreib berechn meng wort text berechenbar funktion qed diagonalisierungsverfahr folger funktion beweis gdinfoii satz meng funktion berechenbar abzahlbar meng uberabzahlbar berechenbar funktion verschied algorithm frag vorbereit antwort definition belieb abzahlbar beispiel meng endlich endlich alphabet reell intervall beweis diagonalisier berechenbar funktion primzahl definition beispiel alphabet belieb teilmeng algorithmus meng sprach bijektiv abbild funktion natur zahl derjen dat probl losung klass allgemein determiniert verfahr richtig anfangsdat elementar schritt halt losung schreibweis funktion mathemat sinn achtung turing-maschin moglich algorithmus intuitiv sinn definition meng beispiel folg belieb belieb endlich kellerautomat wesent eigenschaft algorithmus verfahr spezialfall losung gross klass problemausprag wiederholt ausfuhr verfahr gleich eingab fuhr beschreib endlich zulass fuhrt schritt schritt zeit berechenbar entscheidbar intuitiv sinn algorithmus beschrieb verfahr ausgab zulass eingab schritt halt terminier programm endlich lang abstrakt informat bemerk sprach angegeb grammat typ frag kapitel beweis existenz sprach passend antwort gestellt frag ausdrucksfah typ- sprach metisch ausdruck belieb klammerschachtel ausreich realist programmiersprach kontextfrei grammat kontextsensitiv komponent beispielsweis anforder programm verwendet variabl semant erkennungsaufwand aufwand syntakt korrekt programm lang progamm determinist exponentiell erkennungsaufwand beschreib bandinschrift konfiguration definition inhalt band zeich feld aktuell sl-kopf leerfeld liegend leerfeld tupel aktuell eingabealphabet bandalphabet zustandsmeng partiell funktion anfangszustand endzustand definition turing-maschin endlich automat unend arbeitsband sequentiell tupel meng zusammenhang kontextsensitiv grammat lba zwischenschritt auftret wort generiert bandinschrift repeat recht regelseit band link seit regel until monotoni beschrankt teil band modelliert begrenzungssymbol uberschritt lang verfugbar bandabschnitt hangt jeweil eingabewort automat fahig satz nach turing-maschin linear bandbeschrank turing maschin akzeptier turing-maschin gdinfoii such aktuell bandinschrift teilwort akzeptier typ- grammat simulation regeln einzel beweis buch hopcroft gdinfoii leicht endlich automat aquivalent kellerautomat satz beweiside typ- nichtdeteminist turingmaschin meng regeln ableit wort ruckwart beispiel kellerautomat turing-maschin ide link schritt tabell sprach turing-maschin definition wort akzeptiert klass turing-maschin erkannt bemerk halt turing-maschin akzeptor fragestell eingabewort definition turing-maschin anfangskonfiguration zeich bandinschrift akzeptier endkonfiguration folgekonfiguration moglich hervorrufbar reflexiv-transitiv hull relation bemerk sprach angegeb grammat typ frag kapitel beweis existenz sprach passend typ--grammat typ- typ--sprach allgemein sprach erinner chomsky-grammat grammat typ- phasenstrukturgrammat bemerk ableit wort erzeugt zeichenkett kurz korollar gdinfoii satz beweis kontextfrei grammat typ--grammat regeln neu nonterminalsymbol fug resultier sprach beispiel seit qed bemerk aufwand wort kontextsensitiv lang monoton grammat definition chomsky-grammat regeln form wort anwend regel satz monoton aquivalent kontextsensitiv beweis gdinfoii kontextsensitiv typ--sprach sprach typ--grammat grammat beispiel erinner produktion form recht seit regeln abab abc regel