Automatentheorie und formale Sprachen
Results 1 to 2 of 2
  1. #1

    Title
    Veteran
    Join Date
    Jul 2002
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Unhappy Automatentheorie und formale Sprachen

    Hi,
    ich hab ein großes Problem. Ich muß eine Aufgabe in Automatentheorie und formale Sprachen lösen, komme aber nicht weiter...Informatiker müssten das Fach eigentlich kennen. :wink:
    Das Thema ist Kontextfreie Sprachen, Pumping Lemma für KFS. :???:

    Nun zur Aufgabe:
    ---------
    Zeigen Sie, dass die folgende Sprachen kontextfrei sind:
    1. { a m b n c m + n – k d k | m, n, k ≥ 0 }
    2. { a n b m | n ≠ m }
    ---------

    ...da es leider nicht richtig angezeigt wird hab ich die Aufgabe mal anders gespeichert.



    oder als pdf

    Download

    Für jede Hilfe bin ich dankbar. :santa:
    cu

  2. #2

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich bin gerade am theoretiche inforatik1 -lernen, da kommt das auch vor. ich probier mal dein 2. beispiel:

    { "a"^n "b"^m | n != m }

    Zum Beweis würde ich am einfachsten eine kontextfreie Grammatik angeben, die diese Sprache erzeugt:

    <Wort> := "a" <mehr_a_als_b> | <mehr_b_als_a> "b"

    <mehr_a_als_b>:= "a" <und_noch_mehr_a> "b" | epsilon
    <und_noch_mehr_a>:= "a" <und_noch_mehr_a> | epsilon

    <mehr_b_als_a>:= "a" <und_noch_mehr_b> "b" | epsilon
    <und_noch_mehr_b>:= <und_noch_mehr_b > "b" | epsilon

    , wobei epsilon das Leerwort ist.

    Ich denke, damit müsste sich die 2. Sprache beschreiben lassen, und da die Grammatik offenbar kontextfrei ist (auf der linken Seite keine Terminalsymbole), ist es die damit beschriebene Sprache auch..

    hth, (und es ergibt sinn)
    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •