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:
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
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]
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
Grüße,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.
Wolti
Last edited by wolti; 01-05-2003 at 15:27.
Friends don't let friends drink and su(1) -- Kevin Harris
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
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
Posting Permissions
Reply With Quote
Bookmarks