You are not logged in.

migu

free rider

  • "migu" is male
  • "migu" started this thread

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

1

Tuesday, January 15th 2002, 7:12pm

Theo Inf I - Blatt 11

Hallo zusammen,

jetzt dreht sich mir mein Hirn um, denn:

Das elfte Übungsblatt für Theor. Inf. I will schließlich von mir gelöst werden.
Bloß wie?

Zu Aufgabe 2:
Heute in der Übung war die Konstruktion eines TA, der
{ww^R} akzeptiert, noch verständlich und plausibel.

Doch wie lasse ich den Automaten {ww} akzeptieren?
Muss man da nicht die Mitte des Wortes finden?
Wie nur?

Ach, mir geht's gar nicht gut!

Schreibt doch bitte mal eure zahlreichen genialen Lösungen. ;-))

migu
tar: Anlegen eines leeren Archivs wird feige verweigert.

Zypressen Hügel

Junior Schreiberling

Posts: 244

Date of registration: Dec 22nd 2001

2

Wednesday, January 16th 2002, 7:39am

Meine Idee war, das erste Zeichen (0 oder 1) zu lesen und mit einem a oder b zu überschreiben und sich über einen Extrazustand zu merken, was ich überschrieben habe. Dann lass ich den Kopf bis zum letzten Zeichen laufen und überschreibe das mit A oder B und fahre zurück zum 1. noch nicht ersetzten Zeichen (indem man zurück fährt, bis das Zeichen unter dem Lesekopf ein a oder b ist und dann einen Schritt nach rechts geht)
#0100101001# --> ... #ab001010AB# -> ... #abaabABAAB#
Vorteil: Die Mitte des Wortes ist zu erkennen. Jetzt muss man nur noch das 1. Zeichen lesen und bis zum ersten Großbuchstaben gehen und prüfen, ob die Zeichen sich entsprechen... Rest kriegst du sicher selber hin, irgendwie.
Hoffe, ich konnte dir helfen, Gruß Eike
Man kann auch ohne Spass Alkohol haben 8)

migu

free rider

  • "migu" is male
  • "migu" started this thread

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

3

Wednesday, January 16th 2002, 8:50am

Genial!

Quoted

Original von Zypressen Hügel
#0100101001# --> ... #ab001010AB# -> ... #abaabABAAB#
Vorteil: Die Mitte des Wortes ist zu erkennen. Jetzt muss man nur noch das 1. Zeichen lesen und bis zum ersten Großbuchstaben gehen und prüfen, ob die Zeichen sich entsprechen... Rest kriegst du sicher selber hin, irgendwie.

Hoffe, ich konnte dir helfen, Gruß Eike


Oh ja!
Das ist ja genial einfach. Danke dir!
(Die zündende Idee ist alles.)

Michael
tar: Anlegen eines leeren Archivs wird feige verweigert.

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

4

Wednesday, January 16th 2002, 9:25pm

Findich auch geil...HURRA

geschickt geschickt...ich hats anders, sehr viel einfacher...aber ok, ich machs auch mal so, wennde willst...

aufgabe 1 habich auch recht wenig....
können das hier alle oder warum fragt keiner....
scheiss kubismus

Danke
Wolfram

PS: ich konnt ma lightning strikes mitsingen

AnAlien

Praktikant

  • "AnAlien" is male

Posts: 7

Date of registration: Jan 16th 2002

5

Wednesday, January 16th 2002, 9:50pm

mitte finden ist auch meine idee. aber ich hab keinen schimmer...

Zypressen Hügel

Junior Schreiberling

Posts: 244

Date of registration: Dec 22nd 2001

6

Wednesday, January 16th 2002, 9:56pm

@InformatikMinister

Geht auch einfacher, hab nämlich den "Fehler" gemacht, nichtdeterministisch mit deterministisch zu verwechseln... *groll*
Man kann auch ohne Spass Alkohol haben 8)

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

7

Wednesday, January 16th 2002, 10:34pm

und wo hilft das jetzt gross weiter ? ich zermatsch mir da auch grade die birne drüber...

Zypressen Hügel

Junior Schreiberling

Posts: 244

Date of registration: Dec 22nd 2001

8

Wednesday, January 16th 2002, 10:50pm

Angenommen, man hätte nun ein Wort #abaabABAAB# und der Lesekopf steht unter dem ersten a. Man liest das Zeichen, überschreibt es wieder mit 0 oder 1 und geht in einen Zustand S0 oder S1, je nachdem was man gelesen hat, und geht solange nach rechts, bis ein großes Zeichen gelesen wird. Angenommen, man hätte ein a gelesen und befindet sich entsprechend im Zustand S0. Man geht nach rechts bis zum ersten großen Zeichen. Ist das ein "A", überschreibt der Automat das "A" mit z.B. einem "C" bzw "D". #0baabCBAAB# mit Lesekopf auf dem "C". Dann geht man zurück bis zur ersten Ziffer, einen nach rechts und liest das Zeichen usw. wie oben: #01001CDCCD# Geht nun der Automat zurück bis zur (aus Leserichtung) ersten Ziffer und dan auf das Zeichen rechts daneben und ist das Zeichen dann ein "C" oder "D", ist das Wort akzeptiert. Ansonsten ist der Automat irgendwann vorher schon stehengeblieben.
War jetzt die Kurzfassung, ich hoffe, es hilft trotzdem.
Gruß, Eike
Man kann auch ohne Spass Alkohol haben 8)

PeeMan

Trainee

Posts: 52

Date of registration: Jan 9th 2002

9

Wednesday, January 16th 2002, 10:51pm

hat wer nen plan wie man bei 1.b) von einer kontext-sensitiven sprache eine kontextfreie abzieht ?( ..komische aufgabe mal wieder!

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

10

Wednesday, January 16th 2002, 10:59pm

thanks eike, aber ich krieg hier die krise : bastel ich das grade nobel in excel vor mich hin, fliegt hier die sicherung raus. tolle wolle. jaja, werden die experten unter euch sagen : klar hatte ich autosave an, bin ja auch kein milchbonbonlutscher, aber ratet mal welche datei norton als unrecoverable entdeckt ? AAA RRR GGG HHH ! (das war keine wortfolge, das ist ein aufschrei!)

ich stokel mir jetzt hier nochmal irgendetwas halbwegs sinniges aus den fingern, und hau mich dann pennen, muss morgen fryh arbeiten (von wegen faule studenten...)

thanx & n8 !

Zypressen Hügel

Junior Schreiberling

Posts: 244

Date of registration: Dec 22nd 2001

11

Wednesday, January 16th 2002, 11:07pm

@peeman

Man zieht nicht eine Sprache von der anderen ab, sondern die Klasse der kontextsensitiven von der Klasse der kontextfreien Sprachen. Man zeigt also in der Aufgabe, dass die Sprache nicht kontextfrei ist, also nicht Teil der kontextfreien Sprachen und dann zeigt man, dass eine kontextsensitive Grammatik existiert, die die Sprache erzeugt. Am besten, indem man eine kontextsensitive Grammatik zusammenbaut, die die Sprache erzeugt.

Gut's Nächtle, Eike
Man kann auch ohne Spass Alkohol haben 8)

Zypressen Hügel

Junior Schreiberling

Posts: 244

Date of registration: Dec 22nd 2001

12

Wednesday, January 16th 2002, 11:08pm

Quatsch, man zieht die Klasse der kontextfreien von der Klasse der kontextsensitiven Sprachen ab... Ist schon Schlafenszeit...

Man kann auch ohne Spass Alkohol haben 8)

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

13

Wednesday, January 16th 2002, 11:15pm

Nochmal zum mitschreiben...

Also im ersten durchlauf wird abwechselnd von vorne und hinten 0->a|A und 1->b|B

danach kann man doch zur mitte wechseln...also wenner keine 0|1 mehr findet (kann man ja nach links zurücklaufen lassen mit der einschränkung dass, wenn er a|b liest (ohne 0|1 vorher...wieder zustandswechsel dabei) direkt in den zustand wechselt, wo er weiss, dass das wort fertig umgewandelt ist)

und von vorne nach hinten vergleichen, wobei man alle abgehandelten symbole z.B. zu c macht
dann hin und her mit c jeweils als "endstück" und fertsch wenn er von einem c nach links geht und direkt wieder nen c liest

so stell ich mir das vor....denke mir, es geht, weiss aber nich obs immernoch so gut klingt wennichs niederschreibe

aufgabe 1 habich noch nix wirklich....blöd

ewiger dank
der eh über 66%ige 8)
Wolfram


PeeMan

Trainee

Posts: 52

Date of registration: Jan 9th 2002

14

Wednesday, January 16th 2002, 11:26pm

Wunderbar

jetzt raff auch ich datt :)

dange Henning

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

15

Wednesday, January 16th 2002, 11:30pm

auch, wenn jetzt keiner mehr antwortet...

mal generell...was kann man denn mit nicht deterministisch anfangen

bedeutung ist klar, aber ich find da jetzt keine verwendung für...ehmmmm, nee

so geordnet eins nachm andren findich schon ok

Gut Nacht

PS: heisse garnich Henning :P

PeeMan

Trainee

Posts: 52

Date of registration: Jan 9th 2002

16

Wednesday, January 16th 2002, 11:31pm

scheissendreck dann muss wohl wieder gepumpt werden :(

ps. das ging auch an Eike ;)

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

17

Wednesday, January 16th 2002, 11:39pm

So hab ichs gemacht jetzt endgültig

Noch nicht fertig mit abschreiben, aber so läufts meiner aktuellen Meinung her:

erstes "w" von vorne durch a´s und b´s tauschen (für 0´s und 1´s :rolleyes: ) und zweites "w" von hinten durch A´s und B´s
dann nach der A|B ersetzung checken, ob allesgetauscht wurde, also einen nach links und gucken obs nen a|b ist, wenn ja ist man praktischerweise in der mitte und kann (das hab ich jez noch nich aufgeschrieben) aus der mitte heraus anfangen (also am anfang vom zweiten wort) anfangen abzugleichen

das grade getauschte symbol zu c machen und annen anfang zurück und erstes hoffentlich a bei A und b bei B zu c machen
zurück zum ersten A|B und so weiter
und immer durch c´s ersetzen damit man nicht an den # in der mitte "hängenbleibt"

und dann läufts bis er beim nach rechts laufen zu keinem A|B kommt, sondern zu nem #

und dann solltes fertig sein

kompliziert, aber wie gesagt nicht deterministisch kapier ich da grad nich

ich bin mir im moment keines denkfehlers gewar....

lange rede kurzer sinn, schöne nacht noch

nich leicht, nich leicht alles
aber son ganzes thema an einem beispiel...bring auch nich wirklcih übung X(

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

18

Wednesday, January 16th 2002, 11:40pm

Dacht ich mir

Dass ich nich gemeint bin, binich ja nie ;(

doch eher Balkon statt Bett jetzt 8o

PeeMan

Trainee

Posts: 52

Date of registration: Jan 9th 2002

19

Wednesday, January 16th 2002, 11:50pm

mal was ganz anderes

was bist denn du eigendlich fürn geiles tier ?!
sieht aus wie hund mit feldhamster gekreuzt :D :D :D

rockt aber

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

20

Wednesday, January 16th 2002, 11:54pm

Representin´, representin´

das ist einer von 100 maulwürfen aus einer folge der absolut bahnbrechenden 5minuten serie aus GB, die komplett ohne jeglicher regel oder periode folgend auf SuperRTL läuft:

Der Hase von nebenan!

Liebenswerte Minimalistik sag ich nur...blabla

Find ich voll geil.