Grammatik für Sprache finden < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | 6. Durch den regulären Ausdruck 0*11* ist eine Sprache gegeben.
a) Geben Sie eine kontextfreie Grammatik an, die dieselbe Sprache generiert. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Meine Lösung wäre Folgende;
S [mm] \to [/mm] A | B
A [mm] \to [/mm] 0*C | [mm] \varepsilon
[/mm]
B [mm] \to [/mm] 1*C | [mm] \varepsilon
[/mm]
C [mm] \to [/mm] 1C | 0C | *C | [mm] \varepsilon
[/mm]
Aber ich glaube die Lösung ist falsch. Gibt es nur explizit eine Lösung und wie gehe ich am besten "Systematisch" vor, falls das überhaupt geht? Muss ich die Sprache/Wort eventuell einteilen ?
Es ist ja immer die Rede von Kontextfrei, was das aber bedeutet kann ich in diesem Fall nicht eroieren.
LG
micha
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:47 Mo 15.03.2010 | | Autor: | Rino |
Was machen denn die * in deiner Grammatik?
Der reguläre Audruck erzeugt eine Sprache [mm] $G=\lbrace 0^n1^m| n\ge0, m\ge1\rbrace$ [/mm] (mit [mm] $0^n=\underbrace{0...0}_{n-\text{mal}}$)
[/mm]
Eine Grammatik wäre zum Beispiel:
[mm] $S\mapsto [/mm] A1B $
[mm] $A\mapsto 0A~~|~~\epsilon$
[/mm]
[mm] $B\mapsto 1B~~|~~\epsilon$
[/mm]
kontextfrei heißt hier, dass die Nicht-Terminal-Symbole auf der linken Seite der Position "frei" stehen, d.h. zum Beispiel nicht sowas wie $0A [mm] \mapsto [/mm] 1$
Schöne Grüße,
Rino
|
|
|
| |
|
Die * sind vorgegeben und gehören auch dort hin. Unser Professor scheint es anscheinend zu lieben solche + * und was auch immer mit herrein zu nehmen, hat also alles seine Richtigkeit.
Die Frage ist dann, wenn man es als Zeichen wie 1 und 0 ansieht, wie die Grammatik dann aussieht und ab da verstehe ich es nicht mehr.
Lg
Micha
|
|
|
| |
|
Hallo Micha,
ich denke Rino meint, was das * in Deiner Grammatik! zu suchen hat.
> Die * sind vorgegeben und gehören auch dort hin. Unser
Im regulären Ausdruck sind die durchaus OK, aber nicht in der Grammatik.
> Professor scheint es anscheinend zu lieben solche + * und
> was auch immer mit herrein zu nehmen, hat also alles seine
> Richtigkeit.
Weißt Du denn auch, was beispielsweise das * bedeutet?
Stichwort: Kleene-Stern.
> Die Frage ist dann, wenn man es als Zeichen wie 1 und 0
> ansieht, wie die Grammatik dann aussieht und ab da verstehe
> ich es nicht mehr.
Nach dieser Frage scheint mir nämlich nicht so. [mm] 0^{\*} [/mm] bedeutet sozusagen
beliebig oft die Null. Also Du hast
[mm] 0^{\*} 11^{\*}
[/mm]
Nun überlegst Du Dir wie der Aufbau hier ist, d.h. jedes Wort hat mind. eine 1.
Also sind Elemente der regulären Sprache:
1, 01, 011, 001, 001111 usw
Hilft Dir das schon?
Gruß,
Anna
|
|
|
| |
|
Okay, jetzt habe ich es verstanden! Vielen Dank an euch beide, jetzt sagt mir der Stern auch was, leider nimmt unser Professor auch den Stern in der Mitte der Zeichen wie das [mm] \* [/mm] und dann hat es leider beim Parsebaumzeichnen eine andere Bedeutung. Glaube ich ^^
Was ich noch nicht verstehe ist wie dieser Ausdruck zu Stande kommt, der macht mir beim Pumping Lemma immer noch Probleme und ich komme einfach nicht vorran, weder mit Fachliteratur noch mit dem Internet -.-
$ [mm] G=\lbrace 0^n1^m| n\ge0, m\ge1\rbrace [/mm] $ $ [mm] 0^n=\underbrace{0...0}_{n-\text{mal}} [/mm] $
|
|
|
| |
|
Hallo Micha,
> Was ich noch nicht verstehe ist wie dieser Ausdruck zu
> Stande kommt, der macht mir beim Pumping Lemma immer noch
> Probleme und ich komme einfach nicht vorran, weder mit
> Fachliteratur noch mit dem Internet -.-
>
> [mm]G=\lbrace 0^n1^m| n\ge0, m\ge1\rbrace[/mm]
> [mm]0^n=\underbrace{0...0}_{n-\text{mal}}[/mm]
Das ist einfach Deine o.g. Sprache. Wir haben ja schon festgestellt, dass diese aus mindestens einer 1 besteht - mit beliebig vielen 0 davor und beliebig vielen 1 danach.
Also [mm] 0^n [/mm] mit n [mm] \ge [/mm] 0 und [mm] 1^m [/mm] mit m [mm] \ge [/mm] 1, wobei das hoch n halt wie von Rino schon erklärt heißt: n-mal die 0, also [mm] 0^n [/mm] mit n = 5 wäre beispielsweise 00000.
Gruß,
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:44 Mo 15.03.2010 | | Autor: | Giesskanne |
Ahhhh okay,
jetzt habe ich es verstanden.Das hilft mir auch ein wenig bei Pumping Lemma weiter, aber ich denke bis Morgen um 14 Uhr verstehe ich das nicht mehr. :D
Vielen Dank an alle.
Lg
micha
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:59 Mo 15.03.2010 | | Autor: | Anna-Lyse |
Hallo Micha,
> bei Pumping Lemma weiter, aber ich denke bis Morgen um 14
> Uhr verstehe ich das nicht mehr. :D
wer weiß  Frag' doch einfach, was konkret Dir unklar ist.
Gruß
Anna
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:26 Di 16.03.2010 | | Autor: | Giesskanne |
Ich werde die Frage später nach der Klausur nochmal stellen, oder vielleicht doch nicht. Eventuell ärgere ich mich dann das ich so etwas " einfaches " nicht verstanden habe. Denn bis jetzt war alles mehr oder weniger einfach, man brauch die richtige Erklärung und ein wenig Schmalz *g*
lg
micha
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:02 Di 16.03.2010 | | Autor: | Anna-Lyse |
Hallo Micha,
OK, dann viel Glück bei der Klausur. 
Gruß
Anna
|
|
|
|
