Announcement

Collapse
No announcement yet.

Beispiel zum Üben - Automaten

Collapse
X
  • Filter
  • Time
  • Show
Clear All
new 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 Files
    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
    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 Files
    Last edited by Flowyes; 01-05-2003, 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

    Comment


    • #3
      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, 15:27.
      Friends don't let friends drink and su(1) -- Kevin Harris

      Comment


      • #4
        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 Files
        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

        Comment

        Working...
        X