Aufgabe 4.4

[spjoe]

die angegebene Grammatik ist kontext frei (A => beta) somit ist antwort 3 schon mal sicherlich falsch oder?, wenn ma sich die produktion genau überlegt kommt man bzw ich kamm auf die wortform w=a^{2x}b^ya^{3z}\ \ x \ge0, y\g0,z\ge0 aber wie kann ich jetzt weiter vorgehen?

[Auron]

Die angegebene Grammatik ist sogar regulär.
Denn wir können für die erzeugte Sprache einen regulären Ausdruck finden.

{aa}* {b} {aaa}*

Und natürlich können wir auch einen endlichen deterministischen Automaten zeichnen.

Da (1) gilt können (2) und (3) nicht gelten.

[MrGoatee]

m w=a^{2x}b^ya^{3z}\ \ x \ge0, y\g0,z\ge0

wieso kommt da b^y, das kann doch nur 1 mal kommen, oder versteh ich da was ganz falsch?

Mfg MrGoatee

[spjoe]

da hast recht war mein fehler
siehe auron der hat das ganz richtig
lg spjoe

[marioana]

Die angegebene Grammatik ist sogar regulär.
Denn wir können für die erzeugte Sprache einen regulären Ausdruck finden.

{aa}* {b} {aaa}*

Und natürlich können wir auch einen endlichen deterministischen Automaten zeichnen.

Da (1) gilt können (2) und (3) nicht gelten.

bei dem beispiel treten bei mir noch einige unklarheiten auf:

1. frage:
im scriptum s39 1.51 - steht ja, dass man reguläre grammatiken als NEA's zeichnen kann.
"jede Produktion A => aB als Übergang von A nach B mit dem Symbol a, also B element δ(A,a)" darstellbar sei.

nun habe ich das problem, die aktuelle grammatik so aufzulösen. denn gleich zu beginn habe ich die Produktion S => AbB.
weiß das jemand bzw. hat jemand eine tabelle für diese produktionen?


2.frage
mir ist die sprache schon klar, dass diese anhand der grammatik stimmen muss.
{aa}* {b} {aaa}*

jedoch, hat dafür schon jemand einen automaten gezeichnet? kann man pro übergang nur ein symbol nehmen oder kann man auch bei den übergängen beispielsweise "aa" nehmen? denn das reduziert die zustände enorm....


:confused:

[Auron]

1. frage:
im scriptum s39 1.51 - steht ja, dass man reguläre grammatiken als NEA's zeichnen kann.
"jede Produktion A => aB als Übergang von A nach B mit dem Symbol a, also B element δ(A,a)" darstellbar sei.

nun habe ich das problem, die aktuelle grammatik so aufzulösen. denn gleich zu beginn habe ich die Produktion S => AbB.
weiß das jemand bzw. hat jemand eine tabelle für diese produktionen?


Aber nur reguläre Sprachen/Grammatiken kann man als NEA oder DEA darstellen

Für die regluäre Grammatik würde das P dann bei dem Bsp. so aussehen:

P=
{S-> aA | bB , A-> aS, B-> aC | \varepsilon , C-> aD, D-> aB}


2.frage
mir ist die sprache schon klar, dass diese anhand der grammatik stimmen muss.
{aa}* {b} {aaa}*

jedoch, hat dafür schon jemand einen automaten gezeichnet? kann man pro übergang nur ein symbol nehmen oder kann man auch bei den übergängen beispielsweise "aa" nehmen? denn das reduziert die zustände enorm....
:confused:

Ob "aa" sind müsste man mal in der Vorlesung oder beim Tutor nachfragen.
Hab den DE-Automaten mal schnell gezeichnet, gescannt und im Anhang.

Und da es einen DEA zu der Sprache/Grammatik gibt, muss die regulär sein.

[novice]

Wenn man eine Sprache/Grammatik als NEA zeichnen kann, heißt das, dass wir zumindest eine kontextfreie Sprache/Grammatik haben.
Aber nur reguläre Sprachen/Grammatiken kann man als DEA darstellen

Man kann aus jedem NEA einen DEA machen (Satz 1.26 im Skriptum).

[Auron]

Stimmt natürlich, sorry. Hab da nicht genau nachgedacht.
Mag den NEA einfach nicht und wollte ihn wohl als böse darstellen :-P

[marioana]

thx!

ich denke nun ist es mir klar! hatte die grammatik nicht umgewandelt!

:)