 Thema: Paradebeispiel regulär/kontextfrei, folgern |
|
|
Hallo
ist ![[latex]\{a^m b^n : m >= n \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\{a^m b^n : m >= n \}) regulär?
Ich kenne das Paradebeispiel ![[latex]\{a^n b^n :n\in \mathbb{N} \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\{a^n b^n :n\in \mathbb{N} \}) ist nicht regulär, sondern kontextfrei. Ich würde daraus jetzt folgern, daß der Term aus der Aufgabe auch nicht kontextfrei ist, da der Automat für jedes geschriebene a einen Zustand braucht.
Also zunächst einmal behaupte ich ist nicht regulär. Stimmts?
ist ![[latex] \{a^m b^m c^n : m >= n \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php? \{a^m b^m c^n : m >= n \}) kontextfrei?
Auch hier fällt mir sofort das Paradebeispiel ein für kontextsenitive Sprachen
![[latex] \{a^m b^m c^m : m \in \mathbb{N} \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php? \{a^m b^m c^m : m \in \mathbb{N} \}) ist kontextsensitiv, aber nicht kontextfrei.
Jetzt würde ich von der Form darauf schließen, ist nicht kontextfrei.
Könnt ihr mir sagen, ob ich mit meinen Vermutungen richtig liege?
Das würde schon mal sehr helfen
Danke
Phoney
|
|
| Thema: Sprache erzeugen, regülär, kontextfrei? |
|
|
Zu dem Kellerautomaten habe ich allgemein noch eine Frage.
Wir haben da das Beispiel ![[latex] L=\{a^nb^n | n \in \mathbb{N}\} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? L=\{a^nb^n | n \in \mathbb{N}\} )
als Kelelrautomaten gezeichnet
Jetzt haben wir im Startzustand zwei Schlingen gehabt, einmal eine mit
1) a, #/A#
und
2) a,A/AA
wobei wir allgemein a,X/y definierten als: Der Kellerautomat liest a, X ist das oberste Zeichen auf dem Stack, schreibe nun y auf den Stack.
Das heißt also
1) lese a, oberstes Element ist # (unterste Stackzeichen), schreibe A#
2) lese a, oberstes Element ist A, schreibe AA
Jetzt mal als Beispiel für aaa, ich verstehe nämlich die Schlingen in Bezug auf den Stack nicht
aaa, der Kellerautmat geht in 1 rein, weil der Stack noch leer ist
dann ersetzt er # durch A#
Zu bearbeiten ist noch aa, er liest ein a, dann geht er in 2), ersetzt das A durch ein AA
Stackinhalt: AA# (wobei links das oberste Element ist)
dann das letzte a wird gelesen. Gehe in 2), ersetze A durch AA und erhalte
A
A
A
#
Ist das so gemeint?
WEnn ich jetzt aber vom Stack löschen möchte, ohne ein b zu lesen, wie kann man das machen? weißt du das zufällig? Das geht vermutlich gar nicht?
Vom Startzustand in einen anderen Zustand, wobei der PFeil beschriftet ist mit ![[latex]\varepsilon, A/ \varepsilon[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\varepsilon, A/ \varepsilon)
Grüße 
|
|
| Thema: Sprache erzeugen, regülär, kontextfrei? |
|
|
Hallo
Zu dem Zusammenhang mit DEA und NEA und regulären Ausdrücken.
Für
![[latex]G = (\{Z\},\{a,b,c\},\{Z::=abcZ, Z::=\varepsilon\},Z) [/latex]](http://www.matheboard.de/latex2png/latex2png.php?G = (\{Z\},\{a,b,c\},\{Z::=abcZ, Z::=\varepsilon\},Z) )
![[latex]L(G) = \{ (abc)^n : n \ge 0\} [/latex]](http://www.matheboard.de/latex2png/latex2png.php?L(G) = \{ (abc)^n : n \ge 0\} )
ist regulär und kontextfrei. Jetzt kann ich also einen DEA konstruieren. Aber wenn ich jetzt einen Kellerautomaten angeben soll, ist der DEA dann gleichwertig zum Kellerautomaten?
Regeln der Kellerautomaten haben doch immer so eine Form
![[latex]\delta (q_c,\varepsilon,Z_0) -> (q_j, \epsilon) [/latex]](http://www.matheboard.de/latex2png/latex2png.php?\delta (q_c,\varepsilon,Z_0) -> (q_j, \epsilon) )
Beim DEA reicht allerdings schon
![[latex]\delta(q_0,a) = q_1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\delta(q_0,a) = q_1)
Reicht es, einen DEA zu zeichnen um einen Kellerautomaten anzugeben?
Grüße
|
|
| Thema: Sprache erzeugen, regülär, kontextfrei? |
|
|
Hallo Leute!
Es geht um die Grammatik G = ({Z},{a,b,c},{Z::=abcZ, Z::=Epsilon},Z)
Nun soll ich herausfinden, ob L(G) regulär oder kontextfrei ist.
Dafür muss ich ja erst einmal eine Sprache L(G) erzeugen, herleiten oder wie auch immer.
Dass es hier nur (abc)*, kann ich leicht ablesen, daher ist meine Vermutung ja
L(G) = { (abc)^n : n >= 0}
Was habt ihr für Ideen für eine Herleitung dieser Sprache? Dass die Grammatik nur abc beliebig oft erzeugen kann, die Erklärung reicht vielleicht nicht.
Wo wir gerade schon dabei sind. Kann mir vielleicht noch jemand sagen, ob es sich hierbei um eine reguläre oder kontextfreie Sprache handelt? Eins von beidem trifft doch sicherlich zu und ich vermute nach den ersten Überlegungen, dass L(G) kontextfrei ist, aber nicht regulär. Kann mir das jemand bestätigen? Vielleicht seid ihr ja so geübt und könnt das sofort sehen
Grüße
|
|
| Thema: regulären Ausdruck nachweisen |
Phoney
| Antworten: |
10 |
| Hits: |
10.709 |
|
|
| Zitat: |
Original von JROppenheimer
Reicht es nicht, ein Wort zu finden, dass sich nicht pumpen lässt?
|
Das würde ich auch gerne wissen 
Tobias? Reicht das? 
|
|
| Thema: regulären Ausdruck nachweisen |
Phoney
| Antworten: |
10 |
| Hits: |
10.709 |
|
|
Soweit kann ich das nachvollziehen.
Aber
| Zitat: |
Ich glaube, man kann den Beweis, dass deine Sprache nicht kontextfrei ist,
|
Es verwirrt mich, dass du von kontextfrei redest, ich aber regulär nachweisen muss. Kann ich denn nicht das Pumpinglemma vom Typ 3 für regulär benutzen?
|
|
| Thema: regulären Ausdruck nachweisen |
Phoney
| Antworten: |
10 |
| Hits: |
10.709 |
|
|
Das mit dem Pumpinglemma für reguläre Sprachen ist echt ein toller Tip. Das hatten wir, den anderen Satz leider nicht.
Kannst du mir denn sagen, wann ich den für L3 und wann den für L2 nehmen muss? Ich hätte nämlich das für L3 genommen.
So ganz blick ich da noch nicht durch
Gruß
Phoney
|
|
| Thema: regulären Ausdruck nachweisen |
Phoney
| Antworten: |
10 |
| Hits: |
10.709 |
|
|
Hallo
L={x aus {a,b}* }: Die Anzahl der a in x ist größer als die Anzahl der b in x}
Handelt es sich hierbei um eine reguläre Sprache?
Wie kann ich das nachweisen? Ich habe mir gedacht, wenn der dazugehörige Automat endlich ist, ist die Sprache regulär. Jetzt kann ich aber einen Automaten basteln, der unendlich viele a zulässt. Aber auch manche, bei denen es nur ein a mehr gibt als b, der wäre dann ja endlich. Aber ich hab kein Plan wie ich das nachweisen soll.
Hoffe auf zahlreiche Tips, Danke 
|
|
| Thema: regulärer Ausdruck umwandeln |
|
|
Was heißt denn mit e-Übergängen gibts die auch ohne bei der Thompson-Konstruktion?
Wenn ich umgekehrt einen DEA habe, wie wandel ich es dann in einen regulären Ausdruck um?
Muss doch eigentlich nur von DEA zum Thompson-Automaten. Gibts da auch ein Schlagwort?
Danke
|
|
| Thema: regulärer Ausdruck umwandeln |
|
|
Hallo
Hier ist ein regülärer Ausdruck gegeben ((a* vereinigt b*)ab)*
Also erst einmal ist mir die Bedeutung nicht klar
a* bedeutet ja so viel wie: es können beliebig viele a kommen, 0,1,2,3,4...
b* das gleiche
(ab)* würde z.b. bedeuten ababababab.
Was genau bedeutet jetzt die Vereinigung?
Jetzt habe ich die Aufgabe, aus diesem Ausdruck einen DEA zu erstellen. Wie geht man da am geschicktesten vor?
Grüße von Phoney
|
|
| Thema: Präfix und Postfix |
Phoney
| Antworten: |
9 |
| Hits: |
12.790 |
|
|
Echt? Das überrascht mich jetzt aber. Die Tiefensuche funktioniert dann immernoch und ich erhalte dann auch noch immer die Präfixform? Hätte ich jetzt nicht gedacht.
Danke
|
|
| Thema: Präfix und Postfix |
Phoney
| Antworten: |
9 |
| Hits: |
12.790 |
|
|
Danke für die recht ausführliche Erklärung. Eine Frage habe ich aber noch
Wäre auch (5*2) + ((9/10)+4) möglich? Also dass der Baum wir die Plus 4 in den rechten Ast schreiben und dort ein Übergewicht haben? Also quasi wie der Linke Ast, nur dass wir auf der Rechten Seite jetzt
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
|
+
4 /
9 10
|
|
Das dürfte eigentlich nicht funktionieren, oder? Warum das Übergewicht im linken Ast, also warum ist der linke Ast länger als der REchte?
|
|
| Thema: Präfix und Postfix |
Phoney
| Antworten: |
9 |
| Hits: |
12.790 |
|
|
Nein, hier weiß ich leider nicht, wie man einen Baum aufstellt.
Ich meine, da steht etwas von Plus und so, wie soll ich das denn da einbrigen? Mir fällt da nur spontant die Regel ein, alles was größer dem Wurzelelement ist, sollte im rechten Zweig stehen, alles was kleiner gleich ist unten links. Aber im Graph dürfte die Wurzel hier ja ein Plus sein... Warum auch immer?
Wie stellt man denn den Baum zur Infix-Notation auf?
|
|
|
