Theo Inf I - Blatt 11 - Grundlagen der Informatik - Fachrat Informatik

migu

free rider

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.

Go to the top of the page

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

Go to the top of the page

migu

free rider

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.

Go to the top of the page

Informatik Minister

Senior Schreiberling

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

Go to the top of the page

AnAlien

Praktikant

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...

Go to the top of the page

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

Go to the top of the page

sebi

Junior Schreiberling

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...

venturemedia.de - you don't need eyes to see, you need a vision

Go to the top of the page

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

Go to the top of the page

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!

Go to the top of the page

sebi

Junior Schreiberling

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 !

venturemedia.de - you don't need eyes to see, you need a vision

Go to the top of the page

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

Go to the top of the page

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

Go to the top of the page

Informatik Minister

Senior Schreiberling

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

Wolfram

Go to the top of the page

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

Go to the top of the page

Informatik Minister

Senior Schreiberling

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

Go to the top of the page

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

Go to the top of the page

Informatik Minister

Senior Schreiberling

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

Go to the top of the page

Informatik Minister

Senior Schreiberling

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

Go to the top of the page

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

rockt aber

Go to the top of the page

Informatik Minister

Senior Schreiberling

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.

Go to the top of the page

Fachrat Informatik - Forum

Theo Inf I - Blatt 11

Genial!

Quoted

Findich auch geil...HURRA

Nochmal zum mitschreiben...

Wunderbar

auch, wenn jetzt keiner mehr antwortet...

So hab ichs gemacht jetzt endgültig

Dacht ich mir

mal was ganz anderes

Representin´, representin´