Results 1 to 4 of 4

Thread: Beispiel zum Üben - Automaten

  1. #1
    Dipl.Ing Flowyes's Avatar
    Join Date
    Dec 2002
    Posts
    1,119
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Beispiel zum Üben - Automaten

    Consider the following NFA (NEA) over the alphabet {0,1}:

    1. Convert this NFA (NEA) to a minimal DFA (DEA).
    2. Write a regular expression for the set the machine accepts.
    3. Write a linear grammar where each right side is of the form aB or a.
    (“a” a terminal and “B” a non-terminal) to generate the set.

    ---

    Sollte nicht so schwer sein

    Der Automat schaut so aus:
    Attached Images Attached Images
    The idea behind this technique is surprisingly simple: just go ahead and do whatever you want to without paying attention to what anybody else is doing. If there is a problem, worry about it later. (Many politicians use this algorithm, too) -- A. S. Tanenbaum, M. v. Steen, Distributed Systems

  2. #2
    Dipl.Ing Flowyes's Avatar
    Join Date
    Dec 2002
    Posts
    1,119
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Als minimaler DEA komm ich hier auf sowas, stimmt ihr mir zu?
    Bei der Ermittlung des regulären Ausdrucks für diese Sprache hab ich aber irgendwie noch Probleme...
    Irgendwelche Ideen, Vorschläge??

    [edit]: dank wolti und dem automaten-tool, krigen wir die lösung schon raus... Dieser Automat ist noch falsch!!![/edit]
    Attached Images Attached Images
    Last edited by Flowyes; 01-05-2003 at 15:00.
    The idea behind this technique is surprisingly simple: just go ahead and do whatever you want to without paying attention to what anybody else is doing. If there is a problem, worry about it later. (Many politicians use this algorithm, too) -- A. S. Tanenbaum, M. v. Steen, Distributed Systems

  3. #3
    Baccalaureus
    Join Date
    Oct 2002
    Posts
    591
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Code:
    Ohne EBNF:
    
    A => 0B | 1C
    B => 0C | 1D | e
    C => 0C | 1B | e
    D => 1D | 0E | e
    E => 1A | 0D
    
    Mit EBNF [korrigiert nochmal, syntax verhaut]:
    
    A => "0"B | "1"C
    B => "1"D | "0"[{"0"}"1"]B | e
    D => {("1"|"00")}D | 0F
    F => 1A
    
    zu B: Der zweite Teil ist der Knoten C zusammengefasst. Hierbei kann
    ich ja einen 0 produzieren und wäre in C (Endzustand). Der Rest wird
    also eine Option. Die andere Möglichkeit wäre 0, beliebige 0, einen 1
    und dann bin ich wieder in B.
    
    Bei D: Beliebig viele 1 oder 00 Folgen kann ich produzieren. Die 00
    wären nach F und wieder zurück. Oder ich gehe mit 0 nach F.
    Grüße,
    Wolti
    Last edited by wolti; 01-05-2003 at 15:27.
    Friends don't let friends drink and su(1) -- Kevin Harris

  4. #4
    Dipl.Ing Flowyes's Avatar
    Join Date
    Dec 2002
    Posts
    1,119
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Und hier ist der Automat...
    Übrigens: ja nicht versuchen bei solchen Beispielen mit den Formeln aus dem Skriptum zu rechnen, um die regulären Ausdrücke zu finden, sondern intuitiv vorgehen.
    Sonst rechnet man mind. eine Stunde lang. Aber der Salzer hat eh schon gesagt, dass die Konvertierung von DEA --> regulärer Ausdruck, bei der Prüfung nicht so schwierig oder kompliziert sein wird. Also keine Sorge
    Attached Images Attached Images
    The idea behind this technique is surprisingly simple: just go ahead and do whatever you want to without paying attention to what anybody else is doing. If there is a problem, worry about it later. (Many politicians use this algorithm, too) -- A. S. Tanenbaum, M. v. Steen, Distributed Systems

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
  •