Turingmaschine < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:27 Mi 03.12.2008 | | Autor: | Yas |
hallo zusammen,
Wenn man Turingmaschine definieren moechte, kann auch so angeben:
TM = (S, E, A, sigma, s0,Blank, F)
TM = ( {s0, s1, s2 ...} , {a,b} , {a,b,0,1,blank} , sigma, s0, blank, {sf} )
also kann man die Arbeits alphabet mehr als die eingabe definieren?
das geht darum diese frage:
Geben Sie jeweils eine deterministische Turingmaschine an, die das Gewünschte leistet. Kommentieren Sie die Überführungsfunktionen.
T1 vertauscht alle as und bs der Eingabe und hält dann.
hier denke ich muss man alle a's -> 0 tauchen und b's -> 1 dann kann jeder 0->b und alle 1's -> a .. hat jemand ander idee?
T2 akzeptiert genau die Binärzahlen, die durch 4 teilbar sind.
hier ist meine problem???? ich habe mir ueberlegt, dass wir wissen schon eine Binaer zahl / 4 ist wenn erste und 2. stelle 0 sind der rest egal !!
aber was macht die TM wenn der 1. oder 2. stelle 1 ist?? bleibt stehen ??
danke vielmals, wenn mir jemand hilfen kann ...
MFG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:45 Do 04.12.2008 | | Autor: | bazzzty |
> hallo zusammen,
> Wenn man Turingmaschine definieren moechte, kann auch so
> angeben:
>
> TM = (S, E, A, sigma, s0,Blank, F)
> TM = ( {s0, s1, s2 ...} , {a,b} , {a,b,0,1,blank} , sigma,
> s0, blank, {sf} )
>
> also kann man die Arbeits alphabet mehr als die eingabe
> definieren?
Nein. Das Arbeitsalphabet ist Teil der Maschine, so wie verschwiedene Binärcodes Grundlage der meisten echten Rechner sind. Man muß eben vorgeben, auf welchem Alphabet die Maschine operiert, und wie die Eingabe kodiert sein soll.
> das geht darum diese frage:
>
> Geben Sie jeweils eine deterministische Turingmaschine an,
> die das Gewünschte leistet. Kommentieren Sie die
> Überführungsfunktionen.
>
> T1 vertauscht alle as und bs der Eingabe und hält dann.
>
> hier denke ich muss man alle a's -> 0 tauchen und b's -> 1
> dann kann jeder 0->b und alle 1's -> a .. hat jemand ander
> idee?
Ich gehe davon aus, daß vor allem erstmal das Alphabet nicht aus "0" und "1" bestehen soll, sondern aus "a" und "b". Und dann muß man eine Überführungsfunktion angeben, die immer das aktuelle Zeichen ändert und dann nach links geht, bis _blank_ kommt. Dann wird angehalten. Dafür reichen zwei Zustände.
> T2 akzeptiert genau die Binärzahlen, die durch 4 teilbar
> sind.
>
> hier ist meine problem???? ich habe mir ueberlegt, dass wir
> wissen schon eine Binaer zahl / 4 ist wenn erste und 2.
> stelle 0 sind der rest egal !!
> aber was macht die TM wenn der 1. oder 2. stelle 1 ist??
> bleibt stehen ??
Also zunächst ist die Frage, wie die Binärzahl auf dem Band steht, mit den "kleinen" oder mit den "großen" Stellen zuerst. Bei Dir stehen jetzt also die kleinen Bits zuerst.
Wie man ablehnt, ist zum Teil Definitionsfrage. Meistens ist das so definiert, daß ein Wort akzeptiert wird, wenn die Maschine in einem Endzustand aus F hält.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 09:31 Do 04.12.2008 | | Autor: | Yas |
Hallo,
also, wie meinst du mit kleinen oder Grossen zahl ?? also binaerzahlen sind 101100101 oder verstehe ich die frage nicht?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Do 04.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:43 Do 04.12.2008 | | Autor: | bazzzty |
Das bezog sich nur auf die Frage, in welcher Richtung man die Zahl auf das Band schreibt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:15 Do 11.12.2008 | | Autor: | Yas |
vielen dank! es hat sich erledigt, meine loesung war richtig duerch deine hilfe ;)
lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:58 Fr 12.12.2008 | | Autor: | bazzzty |
> vielen dank! es hat sich erledigt, meine loesung war
> richtig duerch deine hilfe ;)
> lg
Das freut mich, aber sieh es mal so: Sie war richtig, weil Du nicht einfach aufgehört hast, sondern weil Du nachgefragt hast. Ich sehe regelmäßig genug Stundenten, die das zu leichtfertig hinnehmen, wenn sie etwas nicht aus dem Stand lösen können. Weiter so!
|
|
|
|
