Re: MediaWiki2LaTeX Vortrag

Lieber Dirk,

danke für Antwort u Erklärung. So hatte ich es anhand Deiner Folie nach
einiger Überlegung auch verstanden. Die Anregung, die ich geben wollte, war
ob man evt anschaulich machen kann, dass

(s= (^p [^p )^p]^p ) und (s = uvxyz) und (Forderungen 1-3)

impliziert, dass  \exists n: uv^nxy^nz \not\in L

wobei der Widerspruch hier, wenn ich's recht sehe, für alle n>1 auftritt.

vxy muss kürzer al p sein, und kann damit nach Definition von s nur die
Form K^{q} L^{p-q}  haben, wobei KL nur eine der drei Kombinationen {([,
[), )]} sein kann und q\in{0,...,p}. Damit enthält vy auf jeden Fall p
unbalancierte Klammern (z.B. p-q zuviele öffnende runde und q zuviele
öffnende eckige im ersten Fall usw.) und somit muss für n>1 der Ausdruck
uv^nxy^nz unzulässig sein, da er np unbalancierte Terme enthält,d ie von
den bloss p verbleibenden (in uxz) für n>1 nicht kompensiert werden können.

Wenn diese Überlegung stimmt, könnte man schreiben

s=uvxyz wie oben \implies uv^nxy^nz \in\left\{ (^{p+nq} [^{n(p-q)+q} )^p
]^p,  (^{p} [^{p+nq} )^{n(p-q)+q} ]^p, (^{p} [^{p} )^{p+nq} ]^{n(p-q)+q}
\right\} \not\in L

Und das gilt für jedes L, dass die Regel enthält, dass jede geöffnete
Klammer auch wieder geschlossen werden muss (was nach meinem Verständnis
Dein Ausgangspunkt für  die wiki-tags ist).

Wenn etwas wie der "Widerspruch" in der letzten Formel auf die Folie
gebracht werden könnte, könnte das uU beim Verständnis des beweises helfen.
(Aber das ist natürlich ein für den Vortrag nicht so wichtiges Detail und
vielleicht lohnt der Aufwand daher nicht - ich danke für die Gelegenheit,
darüber emailschreibend nachzudenken ;-)

Grüsse

 Geza










On Tue, Aug 20, 2024, 10:41 Dirk Hünniger <[email protected]> wrote:

> Hallo Geza,
>
> vielen Dank für die vielen Korrekturhinweise. Die Rechtschreibfehler
> habe ich nun behoben. Folie p18 ist in der Tat unübersichtlich.
> Vielleicht kann ich da mit graphviz oder inkscape noch was besseres
> basteln. p22 ist die schwierigste Folie im Vortrag. Das ganze ist halt
> ein Widerspruchsbeweis.
>
> Das Pumping Lemma sagt ja: Wenn eine Sprache kontext frei ist, dann gibt
> es eine Zahl p für die dieser ganze Kram auf der Folie gilt. Was ich nun
> tue, ist, dass ich annehme das es eine solche Zahl p gibt und dann
> zeige, dass der Kram auf der Folie nicht gelten kann. Dafür konstruiere
> ich aus der Zahl p zunächst die Zeichenfolge s= (^p [^p )^p]^p. Weil
> aber die Länge von vxy kleine gleich p ist, kann u v^n x y^n z höchstens
> zwei direkt aufeinander folgende Klammertypen vermehren. Nehmen wir
> zunächst an dies seien ( und [ dann enthält der gepumpte String mehr
> öffnende als schließende Klammern und kann deswegen nicht in L liegen.
>
> Für alles anderen Fälle geht das analog. Wenn da noch Fragen sind, frag
> gerne nochmal, nach.
>
> Viele Grüße Dirk
>
> On 19.08.24 19:30, Geza Giedke (via tex-d-l Mailing List) wrote:
> > Hallo Dirk,
> >
> > danke auch von mir für die Arbeit am Programm und die Folien. Ich
> > finde die Folien klar und konzentriert, an zwei Stellen hab ich etwas
> > gestutzt:
> >
> > * die Folie p18 finde ich sehr unübersichtlich. Kann man die
> > Baumstruktur evt mit Hervorhebungen oder Einrückungen noch sichtbarer
> > machen?
> > * auf p22 hat es mich eine Weile gekostet bis ich (glaube ich) den
> > Beweis gesehen habe (dass es nämlich nicht möglich ist, s= (^p [^p )^p
> > ]^p in der gewünschten Form uvxyz zu schreiben, weil v und y
> > notwendigerweise nicht die gleiche Zahl an öffnenden bzw schliessenden
> > Klammern enthalten können und somit die in 3. definierte Zeichenfolge
> > für n>0 nicht erlaubt ist). Den Bezug zu der Formel am Ende ist mir
> > nicht klar.:
> >
> > * Hier noch für die typo-Liste:
> > - p23: "Korolla" -> "Korollar"; im letzten mal ist einmal "versuchen"
> zuviel
> > - p26: "Vorlagenverbeitung" -> "Vorlagenver*ar*beitung"
> > - p29: "vom den" -> "von den"
> > - und auf der mediawiki2latex website: "devolved" -> "developed"
> >
> > Grüsse
> >   Geza
> >
> > On Fri, Aug 2, 2024 at 3:44 PM Dirk Hünniger <[email protected]>
> wrote:
> >
>
> --
> FAQ: http://texfragen.de/
> Durchsuchbares Archiv: https://www.listserv.dfn.de/sympa/arc/tex-d-l
> Unsubscribe/Verwaltung: https://www.listserv.dfn.de/sympa/info/tex-d-l

-- 
FAQ: http://texfragen.de/
Durchsuchbares Archiv: https://www.listserv.dfn.de/sympa/arc/tex-d-l 
Unsubscribe/Verwaltung: https://www.listserv.dfn.de/sympa/info/tex-d-l