Formale Sprachen

[Nasenbaer]

Hi,
sitze gerade an eine Hausaufgabe für Theoretische Informatik und komm nicht weiter.
Ich soll entscheiden ob es abzählbar viele Sprachen zu einem gegebenen Alphabet gibt oder nicht.

Ich weiß, dass es zu einem Alphabet abzählbar viele Sprachen gibt, die durch eine Grammatik erzeugt werden. Das folgt daraus, dass diese Sprachen zum Chomsky-Typ 0 gehören und das sind aufzählbar viele. Und eine rekursiv aufählbare Menge ist abzählbar.
Aber ich bin mir beim obigen Problem nicht sicher.

Die Frage ist ja eigentlich ob es abzähbar oder überabzählbare viele Teilmenge der Wortmenge E* gibt, wenn E das Alphabet ist. Also im prinzip wie groß die Potenzmenge von E* ist.

[Trap]

Das muss man sich nicht so kompliziert machen, Wörter über beliebigen Alphabeten sind äquivalent/isomorph zu den natürlichen Zahlen (einfach jedes Zeichen als Ziffer betrachten und als n-äre Zahl lesen).

Die Potenzmenge der natürlichen Zahlen ist nicht abzählbar.

[Nasenbaer]

Das muss man sich nicht so kompliziert machen, Wörter über beliebigen Alphabeten sind äquivalent/isomorph zu den natürlichen Zahlen (einfach jedes Zeichen als Ziffer betrachten und als n-äre Zahl lesen).

Die Potenzmenge der natürlichen Zahlen ist nicht abzählbar.
Jo danke das war mittelweile auch meine Idee nur ich war mir nich sicher ob ich nen Denkfehler drin hatte. :)

[Nasenbaer]

Hab noch ein Problem. :/

Ich soll eine Bildungsvorschrift für eine Sprache einer Grammatik angeben bei der alle Wörte die folgende Form haben:

Jedes Wort beginnt mit einer beliebigen Anzahl von (a^nbb)^y.
soll heißen: das a n mal nacheinander gefolgt von 2 b's. und dann wieder n mal das a (diesmal kann n aber ne andere zahl sein) und wieder 2 b's am ende. und das y mal.

und danach kommen noch 2 a's.

Und wie ich den ersten Teil mathematisch korrekt ausdrücken kann weiß ich nicht.
Rauskommen soll dann solche Wörter:

aa, aaabbaabbaa oder abbaaaaabbabbaa usw. halt immer einige a's und dann 2 b's und wieder a's usw. und am ende 2 mal a.

[AlSvartr]

Reicht auch ein Automat? ;) .. mal ganz ohne Form:
Zustände S1,...,S5, Startzustand S1, Endzustand S5

S1:
- a: Bleibe in S1
- b: Übergang in S2

S2:
- b: Übergang in S3

S3:
- a: Übergang in S4

S4:
- a: Übergang in S5

S5:
- a: Übergang in S1
- b: Übergang in S2

n soll doch >=1 sein, richtig?

[Sephiroth]

Also du suchst die Produktionsregeln für eine Grammatik, die diese Sprache erzeugt, richtig?
Wird zu n und y noch etwas gesagt, z.b. das y,n >= 1 oder y!=n etc.?

Die Sprache klingt sehr nach einer Regulären. Reguläre Ausdruck ahoi (a*bb)*

ey toll, zu lange gebraucht um im gedächtnis zu wühlen X-(

[AlSvartr]

Ich glaub der reguläre Ausdruck ist auch ne bessere Idee :D ... das wäre dann tatsächlich (a*bb)* ... ich machs mir manchmal gerne ein wenig schwerer ;D

[Sephiroth]

Ich glaub der reguläre Ausdruck ist auch ne bessere Idee :D ... das wäre dann tatsächlich (a*bb)* ... ich machs mir manchmal gerne ein wenig schwerer ;D
Da hat er nur noch nicht die Produktionsregel, wenn er die sucht. Aus dem Automaten kann man die dafür leicht ableiten.

Aber, ich glaub der Automat ist falsch bzw. die Wörter die Nasenbaer als Beispiele nannte. Denn auf aa endet bei der Sprache kein Wort, sondern immer auf bb.

[Nasenbaer]

Ne es ist eine Grammatik gegeben mehr nicht. Aber die ist durchaus rechtslinear also erzeugt ne reguläre Sprache aber ich soll halt ne Bildungsvorschrift formulieren. Also auch keinen Automaten angeben der die Wörter der Sprache akzeptiert.
Habs erstmal jetzt verbal formuliert. Sie meinte das geht auch wenn es klar formuliert ist. :)

[AlSvartr]

Da hat er nur noch nicht die Produktionsregel, wenn er die sucht. Aus dem Automaten kann man die dafür leicht ableiten.

Aber, ich glaub der Automat ist falsch bzw. die Wörter die Nasenbaer als Beispiele nannte. Denn auf aa endet bei der Sprache kein Wort, sondern immer auf bb.

Hm ja..(a*bb)*aa wärs sonst..hm hm...aber er meinte ja nur, dass jedes Wort mit diesem (a*bb)* beginnt..das mit den 2 a am Ende hat er ja erst später im Post erwähnt..

Ich frag mich allerdings, was man unter ner Bildungsvorschrift zu verstehen hat, wenn es keine Grammatik sein soll..das verwirrt mich ;)

[Nasenbaer]

Ich frag mich allerdings, was man unter ner Bildungsvorschrift zu verstehen hat, wenn es keine Grammatik sein soll..das verwirrt mich ;)

Zum Beispiel für ne andere Grammatik:

L = { a^n b^n, n element von N)

Also alle Wörter die aus n a's gefolgt von n b's bestehen -> ab, aabb, aaabbb, etc.

So eine Bildungsvorschrift halt.

[Nasenbaer]

Das ist das Aufgabenblatt und Aufgabe 3 ist die von der ich rede:

http://wwwteo.informatik.uni-rostock.de/ls_tpp/uebung/serie1.pdf

[Sephiroth]

Das ist das Aufgabenblatt und Aufgabe 3 ist die von der ich rede:

http://wwwteo.informatik.uni-rostock.de/ls_tpp/uebung/serie1.pdf
ach das meinst du X-)

S -> X -> aY -> abbX -> abbaY -> abbaS -> abbaX -> abbaaY -> abbaabbX -> abbaabbaY -> abbaabbaa


Das ist aber keine Bildungsvorschrift für eine Sprache einer Grammatik. Das ist eine Ableitung (eines Wortes). Den dazugehörigen Ableitsungs- bzw. Syntaxbaum kannst du dir dann ja selber aufstellen. ;)

[Nasenbaer]

ach das meinst du X-)

S -> X -> aY -> abbX -> abbaY -> abbaS -> abbaX -> abbaaY -> abbaabbX -> abbaabbaY -> abbaabbaa
Nein das hab ich rausbekommen. War ja einfach. Den 2. Teil der Aufgabe, also die Beschreibung aller Wörter von L(G). Den Beweis nich nur die Beschreibung halt. :)

[Sephiroth]

Nein das hab ich rausbekommen. War ja einfach. Den 2. Teil der Aufgabe, also die Beschreibung aller Wörter von L(G). Den Beweis nich nur die Beschreibung halt. :)
oh ...
das hab ich immer gehasst :tongue: da hab ich immer nur versucht das glaubhaft zu argumentieren, was auch meist gelang :redface:

der start ist klar, mit a fangen alle wörter an (regel S -> X -> aY)
das ende auch, da nur mit der regel Y -> a beendet werden kann, also enden alle auf a.
kleinstes wort ist also aa.
jetzt mußt die nur noch überlegen, wieso nach dem ersten a beliebig viele weitere kommen können, und wie die bb's rein kommen.