Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

zakarumite

Trainee

  • "zakarumite" is male
  • "zakarumite" started this thread

Posts: 56

Date of registration: Feb 15th 2004

1

Monday, March 1st 2004, 11:10am

a^n b^n c^n

hi,
ich hab über nach a^nb^nc^n Grammatik gesucht,aber die Beispiele,die ich gefunden habe,waren nicht korrekt.kann JEmand mir so ein Beisp. geben?
Danke!
...
  • Send private message

schmaidt

Junior Schreiberling

  • "schmaidt" is male

Posts: 159

Date of registration: Feb 25th 2004

Location: Hannover

Occupation: Aus Interesse

2

Monday, March 1st 2004, 11:31am

RE: a^n b^n c^n

hi,

folgende Gramatik tuts für L={a^nb^nc^n | n >= 1}

G=(V,E,P,S) mit E={a,b,c}, V={S,B,C} und
P={S->aSBC,
S->aBC,
CB -> BC,
aB -> ab,
bB -> bb,
bC -> bc,
cC -> cc}

G ist kontextfrei.

Hoffe, hat geholfen.
"Man kann beweisen, daß der technische Fortschritt besser ist mit Zucker!"
Ionesco, Die kahle Sängerin
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

3

Monday, March 1st 2004, 11:49am

RE: a^n b^n c^n

Quoted

Original von schmaidt
G ist kontextfrei.


Eine kontextfreie Grammatik zeichnet sich dadurch aus, dass auf der linken Seite von Regeln nur ein einziges Zeichen stehen darf.
Matthias Galota
  • Send private message

Uprooter

Junior Schreiberling

  • "Uprooter" is male

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

4

Monday, March 1st 2004, 12:15pm

und ausserdem ist a^nb^nc^n mit sicherheit nicht kontextfrei
  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

5

Monday, March 1st 2004, 12:24pm

a^n b^n c^n ist kontextsensitiv, wenn ich mich da richtig erinnere. Steht auch irgendwo bei den Lösungen der Klausuren. Müsste bei den Multiple Choice Fragen gewesen sein. Aber sicher bin ich mir nicht ;)
  • Send private message

Uprooter

Junior Schreiberling

  • "Uprooter" is male

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

6

Monday, March 1st 2004, 12:32pm

die gramm kann man denk ich noch etwas einfacher schreiben:
S->abc
ab->aabB
bB->bbc
Bb->bB
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

7

Monday, March 1st 2004, 1:43pm

Quoted

Original von Uprooter
die gramm kann man denk ich noch etwas einfacher schreiben:
S->abc
ab->aabB
bB->bbc
Bb->bB
Klappt so aber nicht. :)


Beispiel (wir wollen aabbcc ableiten):

S => abc => aabBc => aabbc
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Uprooter

Junior Schreiberling

  • "Uprooter" is male

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

8

Monday, March 1st 2004, 1:53pm

wie hast du denn den letzten übergang gemacht? dafür gibts keine regel..bzw du hast n c nicht bemerkt
bB wird durch bbc ersetzt und nicht durch bb

This post has been edited 2 times, last edit by "Uprooter" (Mar 1st 2004, 1:55pm)

  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

9

Monday, March 1st 2004, 2:00pm

Quoted

Original von Uprooter
wie hast du denn den letzten übergang gemacht? dafür gibts keine regel..bzw du hast n c nicht bemerkt
bB wird durch bbc ersetzt und nicht durch bb
Ups, hast recht. :)

Stimmt aber trotzdem nicht, siehe aaabbbccc. Das ist nämlich nicht ableitbar:

S => abc => aabBc => aaabBBc => aaabbcBc
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Uprooter

Junior Schreiberling

  • "Uprooter" is male

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

10

Monday, March 1st 2004, 2:09pm

hm, hab ich jetzt auch bemerkt:
S->abc
ab->aabB
bB->bbC
Bb->bB
Cc->cc
Cb->bC
CB->BC
das sollte aber gehen, ist dann aber nicht mehr so viel einfacher wie oben :P

This post has been edited 1 times, last edit by "Uprooter" (Mar 1st 2004, 2:14pm)

  • Send private message

schmaidt

Junior Schreiberling

  • "schmaidt" is male

Posts: 159

Date of registration: Feb 25th 2004

Location: Hannover

Occupation: Aus Interesse

11

Monday, March 1st 2004, 2:15pm

oh sorry, stimmt natürlich. Die Grammatik ist kontextsensitiv. Habe ich mich verschrieben. Gibt ja auch einen LBA, der die Sprache akzeptiert. Hatten wir glaube ich in einer Übung.
"Man kann beweisen, daß der technische Fortschritt besser ist mit Zucker!"
Ionesco, Die kahle Sängerin
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

12

Monday, March 1st 2004, 2:54pm

Quoted

Original von schmaidt

Gibt ja auch einen LBA, der die Sprache akzeptiert.


Das stimmt zwar, spielt in diesem Zusammenhang aber keine Rolle. Es gibt nämlich auch für jede kontextfreie Sprache (und damit natürlich auch für jede reguläre Sprache) einen LBA, der sie akzeptiert. Entscheidend ist, dass es keinen Kellerautomaten gibt, der diese Sprache akzeptiert.
Matthias Galota
  • Send private message

zakarumite

Trainee

  • "zakarumite" is male
  • "zakarumite" started this thread

Posts: 56

Date of registration: Feb 15th 2004

13

Monday, March 1st 2004, 8:05pm

zu anbncn lba

könnt ihr auch ein beipiel für lba geben,
man erzählt nur was lba ist, und sagt eie anderer Form von TM?

und noch eine Frage, in der Übung wir haben ein Beispiel für wwR gegebn,
das war nicht det. Kellerautomat. Aber ich habe ncht verstanden wie man
da kontrolliert, dass wir die erste hälfte von einer Eingabe gelesen haben?
...
  • Send private message

Uprooter

Junior Schreiberling

  • "Uprooter" is male

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

14

Monday, March 1st 2004, 8:12pm

gar nicht kontrolliert, der aut fängt ab einer belibigen stelle an, die zeichen zu vergleichen und löschen und wenn er dann zufällig das wort gelesen hat und im endzustand ist, dann wird akzeptiert, wenn nicht, dann fängt er von einer anderen stelle an zu vergleichen und löschen
  • Send private message

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

15

Monday, March 1st 2004, 8:49pm

Er kontrolliert das nicht, er fängt einfach irgendwann an zu löschen.
(ok, dass sthet über dem Post)
Warum: Er ist halt nichtdeterministisch, d.h. wenn einer der tausend Wege zu einem Endzustand führt, ist das Wort akzeptiert. D.h. also, wir nehmen an, er löscht, wenn das erste Wort zu Ende ist. Und wann das zu Ende ist, dass wissen wir. Er nicht. Ist auch egal. Ihn gibts ja eh nur auf dem Papier. :)
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...
  • Send private message