reguläre Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:44 Sa 05.01.2008 | | Autor: | jon |
| Aufgabe | Sei [mm] \IZ [/mm] ein endliches Alphabet. Fuer R [mm] \subseteq \IZ [/mm] x [mm] \IZ [/mm] sei HR = {a1a2 . . . ak | k [mm] \ge [/mm] 2, [mm] (a_i, [/mm] a_(i+1) ) [mm] \in [/mm] R, 1 [mm] \le [/mm] i < k}.
Zeigen Sie, dass HR regulaer ist. |
Also hier habe ich ein endliches Alphabet und zu diesem Alphabet eine Sprache gegeben, nähmlich HR. Ich muss zeigen, dass diese Sprache regulär ist. Das [mm] \IZ [/mm] steht hier für Sigma-Zeichen(habe nicht gefunden, bin neu hier), a1,2,...sind die Symbole, aus denen das Wort der Sprache HR besteht., k natürliche Zahl.
Ich weiss, mann kann zu HR einen DEA(det.endl. Automaten) konstruieren, der diese Sprache akzeptiert. Dies geht ungefähr so: M(HR) - der Automat, der diese Sprache akzeptiert. M(HR) = [mm] (\IQ, \IZ, \delta, q_0, [/mm] F), wobei [mm] \IQ [/mm] - Menge aller Zustände, [mm] \IZ [/mm] - Eingabealphabet, , [mm] \delta [/mm] - die Übergangsfunktion, [mm] q_0 [/mm] - Startzustand, F - Menge aller Endzustände. An dieser Stelle muss ich jetzt diesen Tupel definieren, was das genau ist. Und damit hab ich anscheinend ein Problem...:(
Danke euch im Voraus für die Antwort!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo jon,
Für [mm]k=2\![/mm] gilt [mm]\left(a_1,a_2\right)\in R[/mm].
Für [mm]k=3\![/mm] kann [mm]i=1,2\![/mm] sein; also gilt:
[mm]\left(a_1,a_2\right)\in R\wedge \left(a_2,a_3\right)\in R \Leftrightarrow \left(a_1,a_2,a_3\right)\in\mathcal{Z}\times\mathcal{Z}\times\mathcal{Z}.[/mm]
D.h. letztlich ist das fast die Sprache [mm]\mathcal{Z}^{\*}[/mm] nur das die Mindestlänge eines Wortes hier 2 beträgt. Leider haben wir hier noch das Problem, das R auch Teilmenge von [mm]\mathbb{Z}\times\mathbb{Z}[/mm] sein kann, deswegen gilt wohl nicht immer [mm]\mathcal{Z}=\mathbb{Z}[/mm]. ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]") Wie wäre es mit folgender Definition von [mm]\mathcal{Z}[/mm]?
[mm]\mathcal{Z}:=\{x:(x,y)\in R\}\cup\{y:(x,y)\in R\}[/mm]
Die Idee ist jedes Tupel aus R zu nehmen, es in seine 2 Komponenten aufzuspalten und all' diese "Einzelteile" in eine Menge zu stecken. Durch '[mm]\cup[/mm]' müßten dann alle mehrfach vorkommenden Elemente in dieser Menge verschwinden.
Also wenn ich's mit der Definition hingekriegt habe, dürfte die Aufgabe hier mit einem ![[]](/images/popup.gif) regulären Ausdruck am einfachsten zu lösen sein.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:09 Sa 05.01.2008 | | Autor: | jon |
Hi Karl,
danke für schnelle Antwort.
Ich habe aberleider nicht so ganz verstanden, was du unter Z* verstehst.
Ich habe in der Aufgabenstellung ein [mm] \IZ [/mm] eingeführt und als Sigma-Zeichen definiert. Also das ist nichts anderes als ein Alphabet(endlichem nichtleere Menge von Zeichen). Daher passt deine Definition leider nicht.
Allerdings, man kann zeigen, dass eine Sprache regulär ist, indem man einen regulären Audruck dazu findet.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:21 Di 08.01.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
