You are not logged in.

sommla

Junior Schreiberling

  • "sommla" is male
  • "sommla" started this thread

Posts: 169

Date of registration: Oct 27th 2005

1

Friday, April 6th 2012, 1:37pm

Formale Sprachen - Zustände bei Kellerautomaten

Hi alle zusammen,

wir sitzen schon etwas länger in der Uni und haben schon einige Tafeln hier vollgeschrieben zum Skript zu "Formale Sprachen".

Auf Seite 35, deutsche Skript, steht ein Korollar und zwar

Quoted

(i) Jede kontextfreie Sprache kann von einem Kellerautomaten mit nur einen Zustand akzeptiert werden.
Nehmen wir jetzt dazu die bekannte a^n b^n
Diese Sprache ist auch auf der Wikipedia-Seite als Beispiel angegeben.
Das Beispiel kann man bei Wiki auf 2 Zustände zurückführen, indem man den z2 einfach durch z1 ersetzt am Ende.

Hat aber jemand eine Lösung, wie man den Automaten auf 1 Zustand zurückführen kann, so wie es im Korollar steht?


Danke und Grüße
Lars
Lieber ein Haus im Grünen als 'nen Grünen im Haus.

sommla

Junior Schreiberling

  • "sommla" is male
  • "sommla" started this thread

Posts: 169

Date of registration: Oct 27th 2005

2

Friday, April 6th 2012, 1:48pm

Okey, wir haben einen nicht-deterministischen nach mehreren Stunden gefunden.

ohjeeee!!!
;)

Bei Interesse, poste ich den.
Lieber ein Haus im Grünen als 'nen Grünen im Haus.

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

3

Friday, April 6th 2012, 2:11pm

nach mehreren Stunden gefunden


Genau dabei ist der Lerneffekt am größten. Glückwunsch! :)
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

ogniute

Trainee

  • "ogniute" is male

Posts: 54

Date of registration: Nov 2nd 2005

4

Friday, April 6th 2012, 3:20pm

wo sitzt ihr denn? ich sitze auch gerade im Keller und lern ein wenig

sommla

Junior Schreiberling

  • "sommla" is male
  • "sommla" started this thread

Posts: 169

Date of registration: Oct 27th 2005

5

Saturday, April 7th 2012, 3:37pm

Stahlbausaal
Lieber ein Haus im Grünen als 'nen Grünen im Haus.