reguläre Sprachen

15.01.2013, 16:36

Auf diesen Beitrag antworten »

Nina111

reguläre Sprachen

Meine Frage:
Ich soll zu 2 Sprachen einen endlichen Akzeptor, regulären Ausdruck und eine rechtslineare Grammatik schreiben.

1.L={w?{0,1}* | ?k?N0:Num2(w)=s^k+1}

2. L={0^(3m} U {w10^(3n+2) | w?{0,1}*} mit m,n?N0

Sorry für die unübersichtliche Schreibweise aber ich weiß nicht wie man hier solche Zeichen macht...

Meine Ideen:
Wie man einen endlichen Akzeptor, regulären Ausdruck und eine rechtslineare Grammatik schreibt, nur steh ich grad komplett auf dem Schlauch was für Wörter diese Sprachen überhaupt bildet....
Kann mir jemand helfen?

15.01.2013, 19:22

Auf diesen Beitrag antworten »

Karlito

Hallo,

für das Schreiben solcher Ausrücke kannst du LaTeX verwenden. Das einfachste ist, diesen Editor zu benutzen. Eine andere Variante ist, den Text von mir zu markieren und im Editorfenster einzufügen. Im normalfall werden dann die Bilder durch ihren Quelltext ersetzt.

Damit wir dir helfen können, wäre es günstig, die Ausdrücke noch einmal richtig vorliegen zu haben. Also mach Dir bitte die Mühe, es entweder in LaTeX zu schreiben oder Stelle uns ein Bild zur Verfügung. Wenn Du die Originalaufgabe nicht abfotografieren möchtest, kannst Du sie ja vorher auch abschreiben.

Gerade für die Sprache 2 gilt: wenn du einen Automaten für eine Sprache erstellen willst, welche eine Vereinigung aus 2 Teilsprachen ist, dann musst reicht es, für jede Teilsprache einen Automaten zu erstellen und diese geeignet zu verbinden.

Die Grammatik kannst du aus dem Automaten ablesen. Für den regulären Ausdruck gibt es mehrere möglichkeiten. Wahrscheinlich kann man den aber aus der Sprachdefiniton oder dem Automaten ableiten. Dazu aber später weiter wenn du die Definitionen noch mal korrekt wiedergegeben hast.

VG,

Karlito

16.01.2013, 11:29

Auf diesen Beitrag antworten »

Nina111

L={w $[latex]\in [/latex]$ {0,1}* | $[latex]\exists [/latex]$ k $[latex]\in [/latex]$ N0:Num2(w)=2^k+1

L={o^(3m} $[latex]\bigcup [/latex]$ {w $[latex]\in [/latex]$ {0,1}*} mit m,n $[latex]\in [/latex]$ N0

Danke schon mal für deine Hilfe.

16.01.2013, 11:56

Auf diesen Beitrag antworten »

Karlito

Hallöchen,

das ist schon viel besser... Offensichtlich stimmt das aber nicht mit dem ursprünglichen Post überein.

1. $[latex] \mathcal{L} = \{ w \in \{ 0,1 \}^*~|~\exists k \in \mathbb{N}_0 : Num2(w) = 2^k+1 \} [/latex]$
2. $[latex] \mathcal{L} = \{ 0^{3m} \cup \{ w_{10}^{3n+2}~|~w_{10} \in \{ 0,1 \}^* \}~|~m,n \in \mathbb{N}_0 \} [/latex]$

Stimmen die Ausrücke so? Der Existenzquantor vor dem k kommt mir komisch vor...

VG,

Karlito

Anzeige

16.01.2013, 12:04

Auf diesen Beitrag antworten »

Nina111

Die erste Sprache stimmt so, aber die zweite nicht ganz.
In der Aufgabe steht sie so:
$[latex] \mathcal{L} = \{ 0^{3m} } \cup \{ w10^{3n+2}~|~w \in \{ 0,1 \}^* \}~|~m,n \in \mathbb{N}_0 \} [/latex]$

Edit (Karlito): $[latex]\mathcal{L} = \left\{ 0^{3m}\right\}\cup \left\{ w10^{3n+2} | w\in \left\{ 0,1\right\}^* \right\} m,n\in \mathbb{N}_0[/latex]$

16.01.2013, 12:23

Auf diesen Beitrag antworten »

Karlito

Ich passe mal die Beiträge an, damit der Lesefluss gewährleistet ist.

Supi, dann fangen wir mal an:

Wie interpretierst du die erste Sprache?. Welche Bedeutung ordnest du denn der Funktion [latex] Num2(w) [/latex]

[latex] Num2(w) [/latex]

zu?

VG,

Karlito

16.01.2013, 12:48

Auf diesen Beitrag antworten »

Nina111

Naja die Wörter bestehen aus {0,1}* müssen aber in $[latex] Num2(w) = 2^{k}+1 [/latex]$ liegen.

Ich würde sagen w=110 liegt in der Sprache.
$[latex] Num2(110 = 3 = 2^{k}+1 mit k= 1[/latex]$

16.01.2013, 13:13

Auf diesen Beitrag antworten »

Karlito

Prinzipiell richtig interpretiert. Aber:

$[latex] 110_2 = 6_{10} [/latex]$

Schau dir daraufhin noch einmal an, wie die Wörter der Sprache aussehen.

VG,

Karlito

16.01.2013, 13:58

Auf diesen Beitrag antworten »

Nina111

Ich verstehe nicht ganz was du meinst.

Das leere Wort liegt nicht in der Sprache, Wörter die nur aus {0}* bestehen und 10* auch nicht, da $[latex] 2^{0} = 2 [/latex]$ und diese Wörter alle [latex] Num2(w) = 0 [/latex]

[latex] Num2(w) = 0 [/latex]

oder

[latex] Num2(w) = 1 [/latex]

Hingegen liegen 110* und 1010* und 010* und 101* in der Sprache

16.01.2013, 14:05

Auf diesen Beitrag antworten »

Karlito

Hallo,

$[latex]x^0 = 1 \quad \forall x \in \mathbb{N}[/latex]$

Und somit ist [latex] 2^0 [/latex]

[latex] 2^0 [/latex]

definitiv nicht 2!!

[latex]110_2[/latex]

[latex]110_2[/latex]

ist wie gesagt auch nicth 3 sondern 6!
$[latex]1010_2 = 10_{10}[/latex]$ und somt auch nicht in der Sprache!

Du solltest dir dringend noch einmal die Umrechnung zwischen binär und dezimal anschauen.

VG,

Karlito

16.01.2013, 14:29

Auf diesen Beitrag antworten »

Nina111

Ok
0*10 und 0*10*1 liegen in der Sprache. Ist das jetzt richtig?

16.01.2013, 14:31

Auf diesen Beitrag antworten »

Karlito

Nö

Augenzwinkern

Erstmal: was willst du mit den führenden 0en?
Und zweitens: welchen Wert hat die Binärzahl 10?

Edit:
Mach doch mal bitte folgendes: Schreibe die ersten 6 Dezimalzahlen auf, welche in der Sprache sind (k = 0 bis 5) und dazu immer die Binärrepresentation.

VG,

Karlito

16.01.2013, 14:36

Auf diesen Beitrag antworten »

Nina111

Die Binärzahl 10 hat den Dezimalwert 2.

2°+1=2

Also muss 10 doch zu der Sprache gehören oder nicht?

16.01.2013, 14:42

Auf diesen Beitrag antworten »

Nina111

RE: reguläre Sprachen

2=10
3=11
5=101
9=1001
17=10001

w=10, w=11 und alle Wörter 10*1
Ist das jetzt richtig?

16.01.2013, 14:47

Auf diesen Beitrag antworten »

Karlito

Zitat:

Original von Nina111
Die Binärzahl 10 hat den Dezimalwert 2.

2°+1=2

Also muss 10 doch zu der Sprache gehören oder nicht?

Die Umrechnung für [latex]10_2[/latex]

[latex]10_2[/latex]

ist nicht

[latex]2^0 + 1[/latex]

auch wenn das wertemäßig klappt.
$[latex] 10_2 = 1 \cdot 2^1+ 0 \cdot 2^0 = 2_{10}[/latex]$
Aber: $[latex]2 \notin \{ 2^k +1 | k \in \mathbb{N}_0 \} [/latex]$

Nimm es mir nicht übel, aber bitte konzentriere Dich bei den Aufgaben. Ich betreibe das hier nich beruflich. Es ist ein reines Freizeitvergnügen und ich mache das gerne. Du machst ständig Schusselfehler. Ich denke es macht weder dir noch mir Spaß, diese ständig zu korrigieren.

VG,

Karlitio

16.01.2013, 14:54

Auf diesen Beitrag antworten »

Nina111

$[latex] 2^{0}+ 1=2 [/latex]$ war nicht der Umrechnungsweg sondern für k=0.
Und da $[latex] 10_2 = 1 \cdot 2^1+ 0 \cdot 2^0 = 2_{10}[/latex]$ und $[latex] 2^{0}+ 1=2 [/latex]$ ist, müsste 10 doch in der Sprache liegen.

16.01.2013, 14:57

Auf diesen Beitrag antworten »

Karlito

Ohja, entschuldigung, mein Fehler!

16.01.2013, 14:58

Auf diesen Beitrag antworten »

Karlito

Kannst du einen Automaten für diese Sprache angeben?

16.01.2013, 15:17

Auf diesen Beitrag antworten »

Nina111

Wenn der reguläre Ausdruck dann:
$[latex] 1\left(0|0*1\right) [/latex]$ ist, dann sollte der Rest kein Problem sein.
Vielen Dank

Kann ich die zweite Sprache auch so schreiben:

$[latex] \mathcal{L} = \left\{ 000\right\} ^{*} \cup \left\{ 0,1\right\} ^{*}\left\{ 101010\right\} ^{*} \left\{ 1010\right\} [/latex]$

16.01.2013, 15:42

Auf diesen Beitrag antworten »

Karlito

Der reguläre Ausdruck für die erste Sprache Stimmt. Damit hast du alles erschlagen. Aufgrund des Exisitenzquantors würde es aber wahrscheinlich reichen einfach ein einzelnes Wort zu wählen. Schließlich muss es nur ein k geben für dass das Wort in der Sprache ist.

Der erste Teil der ersten Sprache stimmt auch. Der zweite nicht. Ich denke sie lässt sich wohl glaube auch nicht so einfach angeben.

w10 ist ein beliebiges Wort aus der Sprache {0,1}* mit dem Suffix 10. Kniffelig wird es bei der Bedingung, dass sich das 3n+2 mal wiederholen soll, sollte sich aber auch machen lassen.

Erstelle einfach einen regulären Ausdruck für die Sprache w10. Danach für $[latex]w10^{3n+2}[/latex]$ .

VG,

Karlito

16.01.2013, 16:01

Auf diesen Beitrag antworten »

Nina111

w10 müsste (0|1)*10 sein oder?

$[latex]w^{3x0+2}[/latex]$ (0|1)* 1 00
$[latex]w^{3x1+2}[/latex]$ (0|1)* 1 000 00
$[latex]w^{3x2+2}[/latex]$ (0|1)* 1 000 000 00

$[latex]w^{3n+2}[/latex]$ (0|1)*1(000)*00

16.01.2013, 16:12

Auf diesen Beitrag antworten »

Karlito

Sieht gut aus smile

smile

Hier habe ich einen Denkfehler gehabt... Ich wollte den regulären Ausdruck für $[latex](w10)^{3n+2}[/latex]$ erstellen.

Deine Lösung ist richtig. Daumen hoch

Daumen hoch

VG,

Karlito

16.01.2013, 16:15

Auf diesen Beitrag antworten »

Nina111

Super

smile

vielen vielen Dank smile

smile

16.01.2013, 16:16

Auf diesen Beitrag antworten »

Karlito

Jetzt musst du nur noch beide Sprachen verbinden. Im regulären Ausdruck ist das einfach. Bei dem zugeordneten Automaten muss man darauf kommen wie man das macht. Hast du eine Vorstellung?

Und wie sieht es mit den Grammatiken aus?

VG,

Karlito

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »