You are not logged in.

cowhen

Muuuh!

  • "cowhen" is male
  • "cowhen" started this thread

Posts: 1,374

Date of registration: Dec 13th 2001

1

Friday, December 14th 2001, 4:33pm

theo inf I , blatt 9

hallo,

hat irgenwer einen vorschlag für den in aufg. 1 zu entwerfenden kellerautomat?

hab probiert einfach den vom letzen blatt umzubauen, aber das funzt nich. ich schätze man braucht min. 3 zustände, oder?


thx

cowhen
plenty of time to relax when you are dead

RoKu

Trainee

  • "RoKu" is male

Posts: 89

Date of registration: Dec 17th 2001

Location: Lehrte/Europa

Occupation: Informatiker ohne Diplom

2

Monday, December 17th 2001, 2:38pm

Die Zustandsanzahl kann von Lösung zu Lösung variieren, je nachdem wie viele epsilon Übergänge Du hast bzw. ob Dein Automat dertministisch ist.

Wenn es Sinn macht, könnte man hier eine Lösung diskutieren...
Ich könnte ja meine Posten...wenn es denn gewollt ist.
Gruß,

Rolf

"verba volant, scripta manent (discussions get forgotten, just code remains)"

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

3

Monday, December 17th 2001, 11:26pm

Ich find, sollteste machen

Ich würd gern ne Lösung sehen...und gebe dir hiermit freie Hand

Glück auf!

cowhen

Muuuh!

  • "cowhen" is male
  • "cowhen" started this thread

Posts: 1,374

Date of registration: Dec 13th 2001

4

Tuesday, December 18th 2001, 9:03pm

genau!, und...

STUDIEREN (die lösung von anderen) GEHT ÜBER PROBIEREN (selber zu lösen). :D

nee, wir ham die lösung jetzt ja schon persönlich diskutiert, aber poste doch ruhig mal nen ansatz für die anderen.


and dieser stelle nochmal:

thx für die hüüülfe !


cu

plenty of time to relax when you are dead

Informatik Minister

Senior Schreiberling

  • "Informatik Minister" is male

Posts: 1,234

Date of registration: Dec 11th 2001

5

Tuesday, December 18th 2001, 9:15pm

Nicht mein Verdienst

Sind auf jedenfall 2 Zustände nur, von denen der EINE als Startzustand (aber bei weitem nicht nur) fungiert, der ANDERE als Zustand, um "2 Nullen zu garantieren", also erreicht man den durch die Eingabe einer Null, und kann ihn nur durch eine Null verlassen.
Zudem müssen überall noch passend die anderen Übergänge definiert werden, insgesamt sind das 13, pro zustand 6 (0,1 Eingabe x 0,1,Kellersymbol IM KELLER = 2x3 = 6 x 2 Zustände = 12) plus den epsilonübergang in den endzustand (13)...aus dem startzustand

schönen dank Eike
hoffe habs wenigstens richtig verstanden...aber das geht scho

tunay

Zuhörer

Posts: 1

Date of registration: Dec 18th 2001

6

Wednesday, December 19th 2001, 4:48pm

Also! Ich glaube, dass das nicht so ganz stimmt. Du hast schon Recht, dass man einen Zustand braucht, um 2 Nullen zu garantieren. Nur die Zahlen können durcheinander gewürfelt sein. Nach deinem Vorschlag müssen auf jeden Fall zwei Nullen hintereinander stehen. Du sagst man verlässt den Zustand nur dann wenn zweite Null dann kommt. Ist das richtig?
Man kann das Problem mit e-Übergang lösen, aber irgendwie klappt es trotzdem nicht. Also bitte noch ein Vorschlag!!!
Hilfe!!!!!!!

RoKu

Trainee

  • "RoKu" is male

Posts: 89

Date of registration: Dec 17th 2001

Location: Lehrte/Europa

Occupation: Informatiker ohne Diplom

7

Wednesday, December 19th 2001, 4:58pm

also hier meine Aufgabe 1. Jedoch VORSICHT, es ist LAtex code. Wenn Ihr wisst was man damit machen kann, dann gut. Ansonsten versteht Ihr es vielleicht trotzdem.
Sorry.
Anmerkung: \perp ist das bottom symbol, die römischen Ziffern sind nur regelnummern(könnt Ihr vergessen).

Viel Spass.

K=(\{0,1\},\{s_{0},s_{1},s_{2},s_{3}\},\{0,1,\perp \},\delta ,s_{0},\{s_{2}\})mit
\delta =\{
(s_{0},1,\perp ,s_{1},0\perp )^{I}, - Liest eine 1ste(oder
weitere) 1 im Fall \#_{1}(w)*2=\#_{0}(w)
ein und schreibt eine Null (von zwei siehe VIII) auf den
Stack.
(s_{0},1,0,s_{1},00)^{II}, - Liest weitere 1sen ein und schreibt
eine Null (von zwei siehe VIII) auf den Stack. Also wenn
\#_{1}(w)*2>\#_{0}(w)
(s_{0},1,1,s_{0},\varepsilon )^{III}, - Liest eine 1 und
löscht eine 1, wenn \#_{1}(w)*2<\#_{0}(w)
(s_{0},0,\perp ,s_{3},\perp )^{IV}, - Liest eine 1ste (oder
weitere) 0 im Fall \#_{1}(w)*2=\#_{0}(w).
(s_{0},0,1,s_{3},1)^{V}, - Liest 0 im Fall \#_{1}(w)*2\leq \#_{0}(w)
und hält den Stack.
(s_{0},0,0,s_{0},\varepsilon )^{VI}, - Liest weitere 0, und
löscht 0, wenn \#_{1}(w)*2>\#_{0}(w).
(s_{0},\varepsilon ,\perp ,s_{2},\varepsilon )^{VII}, - Wechselt
in einen Endzustand , wenn Wort abgearbeitet und Keller
leer. Also auch \#_{1}(w)*2=\#_{0}(w) gilt.
(s_{1},\varepsilon ,0,s_{0},00)^{VIII}, - Schreibt für eine
gelesene 1, die zweite fehlende 0 auf den Keller (siehe
I+II).
(s_{3},1,\perp ,s_{0},0\perp )^{IX}, - Liest eine 1 im Fall
\#_{1}(w)*2+1=\#_{0}(w) und schreibt die nun fehlende 0
(s_{3},1,1,s_{3},\varepsilon )^{X}, - Liest 1 im Fall \#_{1}(w)*2<\#_{0}(w)
und löscht 1 vom Keller (es fehlt eine weniger!).
(s_{3},0,\perp ,s_{0},1\perp )^{XI}, - Liest eine 0 im Fall
\#_{1}(w)*2+1=\#_{0}(w) und schreibt die nun fehlende 1.
(s_{3},0,1,s_{0},11)^{XII}\} - Liest 0 im Fall \#_{1}(w)*2<\#_{0}(w)
und schreibt die fehlende 1 (für jede zweite gelesene 0
in Folge).
Gruß,

Rolf

"verba volant, scripta manent (discussions get forgotten, just code remains)"

RoKu

Trainee

  • "RoKu" is male

Posts: 89

Date of registration: Dec 17th 2001

Location: Lehrte/Europa

Occupation: Informatiker ohne Diplom

8

Wednesday, December 19th 2001, 5:00pm

Zusatz - Latex:

leq heisst less or equal
geq heisst greater or equal
Gruß,

Rolf

"verba volant, scripta manent (discussions get forgotten, just code remains)"

RoKu

Trainee

  • "RoKu" is male

Posts: 89

Date of registration: Dec 17th 2001

Location: Lehrte/Europa

Occupation: Informatiker ohne Diplom

9

Wednesday, December 19th 2001, 5:04pm

Idee für
Aufgabe 2e.)

Ich habe leider kein Verfahren gefunden, diese Aufgabe genau
zu lösen. Also muss ich mal etwas schwafeln.
Ich vermute L(G) wird nicht von det. Kellerautomaten erkannt.
Ein Automat muss sich zuerst die Anzahl a auf dem Keller
merken, um festzustellen, ob gleich oder ungleich viele
a und b vorhanden sind. Dies geschieht, wenn der Automat
b gegen a vom Keller löscht. Entweder sind noch a oder b
auf dem Keller, wenn c gelesen werden. Im Fall ungleich
viele a und b, kennt der Automat nicht mehr die gelesene
Anzahl b, um eine korrekte Anzahl c zu erkennen. Zumindest
kann er dieses nicht, wenn er nicht "spontan"
entscheiden kann, ob Anzahl a gleich/ungleich Anzahl b ist.

Also vermute ich s.o.
Gruß,

Rolf

"verba volant, scripta manent (discussions get forgotten, just code remains)"

cowhen

Muuuh!

  • "cowhen" is male
  • "cowhen" started this thread

Posts: 1,374

Date of registration: Dec 13th 2001

10

Thursday, December 20th 2001, 9:39am

geht das nich auch so ?? (WICHTIG)

2e)

Wie in (d) gezeigt, handelt es sich bei dem zur gegebenen Grammatik gehörenden Parser um einen nichtdeterministischen Kellerautomaten.

Mit DPDA ist aber die Klasse der Sprachen bezeichnet, die von deterministischen Kellerautomaten akzeptiert werden (Definition 5.13 und Satz 5.15 im Skript).

Also ist L(G) nicht element DPDA(a,b,c) .


Bitte schnell noch antworten!!!

THX, Cowhen
plenty of time to relax when you are dead

RoKu

Trainee

  • "RoKu" is male

Posts: 89

Date of registration: Dec 17th 2001

Location: Lehrte/Europa

Occupation: Informatiker ohne Diplom

11

Thursday, December 20th 2001, 10:25am

Nein, so kann man nicht begründen.
Denn es kann ja trotzdem einen DPDA geben. Dieses wird nicht durch die Existenz eines NDPDA ausgeschlossen (Teilmengenbezihehung).
Gruß,

Rolf

"verba volant, scripta manent (discussions get forgotten, just code remains)"

cowhen

Muuuh!

  • "cowhen" is male
  • "cowhen" started this thread

Posts: 1,374

Date of registration: Dec 13th 2001

12

Thursday, December 20th 2001, 11:49am

thx @ rolf (kwt)

jt
plenty of time to relax when you are dead