Grundl. Endl. Automaten (2) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 17:34 Do 16.02.2006 | | Autor: | mathiash |
| Aufgabe | (1) Definiere die Klasse RE der regulären Ausdrücke über dem Alphabet [mm] \{0,1\}
[/mm]
(zB durch Angabe einer BNF). Definiere die semantische Funktion [mm] \varphi\colon RE\to P(\{0,1\}^{\star}).
[/mm]
(2) Zeige: Zu jedem regulären Ausdruck R gibt es einen äquivalenten NEA A, d.h. mit [mm] L(A)=\varphi [/mm] (R).
Hinweis dazu: Führe den Beweis durch strukturierte Induktion über den Aufbau der reguláren Ausdrücke.
(3) Zeige umgekehrt: Zu jedem DEA A gibt es einen reg. Ausdruck R mit [mm] \varphi [/mm] (R)=L(A). |
Hallo,
Teil 2 einer kleinen, für einen ganz speziellen Adressatenkreis geschriebenen Serie.
Ein Hinweis allgemein, damit nicht Zeit durch etwaige Schwierigkeiten verloren geht:
- Versuch(t), die Fragen so ad hoc zu beantworten. Falls das nicht klappt, so sollte ein Skript
oder so zur Hand genommen werden, dort dann konzentriert und gezielt das nachgeschaut werden, was
zur Benatwortung der Frage notwendig ist.
Pruefungslernen heisst vor allem Konzentration auf das Wesentliche und Trainieren der Intuition, damit
man die Dinge geschickt und kompakt bei sich abspeichern kann und trotzdem nicht den Kopf total zu hat.
Dies als nur einige wohlgemeinte
Anmerkungen....
Mathias
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:19 So 19.02.2006 | | Autor: | Bastiane |
Hallo Mathias...
> (1) Definiere die Klasse RE der regulären Ausdrücke über
> dem Alphabet [mm]\{0,1\}[/mm]
> (zB durch Angabe einer BNF). Definiere die semantische
> Funktion [mm]\varphi\colon RE\to P(\{0,1\}^{\star}).[/mm]
[mm] (\{0,1\}\cup\{(,),+,^{\star}\}\cup\{\emptyset,\Lambda\},\{\},,r) [/mm] mit r:
[mm] ::=0|1|(+)|()^{\star}|()|\emptyset|\Lambda
[/mm]
[mm] \varphi\colon RE\to\cal{P}(\{0,1\}^{\star}):
[/mm]
[mm] \varphi(0)=0
[/mm]
[mm] \varphi(1)=1
[/mm]
[mm] \varphi(\emptyset)=\emptyset
[/mm]
[mm] \varphi(\Lambda)=\{\Lambda\} [/mm] (wieso muss denn hier eine Klammer drum?)
[mm] \varphi(R_1+R_2)=\varphi(R_1)\cup\varphi(R_2)
[/mm]
[mm] \varphi(R_1R_2)=\varphi(R_1)\varphi(R_2)
[/mm]
[mm] \varphi(R_1^{\star})=(\varphi(R_1))^{\star}
[/mm]
für R, [mm] R_1, R_2 \in [/mm] RE
> (2) Zeige: Zu jedem regulären Ausdruck R gibt es einen
> äquivalenten NEA A, d.h. mit [mm]L(A)=\varphi[/mm] (R).
> Hinweis dazu: Führe den Beweis durch strukturierte
> Induktion über den Aufbau der reguláren Ausdrücke.
Mmh - wie mach ich das denn?
> (3) Zeige umgekehrt: Zu jedem DEA A gibt es einen reg.
> Ausdruck R mit [mm]\varphi[/mm] (R)=L(A).
Hierfür müsste doch eigentlich folgendes reichen:
Sei [mm] (S,M,s_0,F) [/mm] ein DEA, dann definiere ich eine BNF folgendermaßen:
für [mm] $s\in [/mm] F$: [mm] s\to\varepsilon
[/mm]
für [mm] M(s,\sigma)=p: $s\to\sigma [/mm] p$
für [mm] $M(s,\sigma)=p\in [/mm] F$: [mm] s\to\sigma.
[/mm]
Aber wie bringe ich das in Worte, was das mit der Aufgabenstellung zu tun hat?
> Teil 2 einer kleinen, für einen ganz speziellen
> Adressatenkreis geschriebenen Serie.
Hat dieser Adressatenkreis vielleicht Mächtigkeit 1? 
> Ein Hinweis allgemein, damit nicht Zeit durch etwaige
> Schwierigkeiten verloren geht:
Mmh - schneller ginge es doch so: ich kann mit der Aufgabe nichts anfangen, also lasse ich es bleiben...
> - Versuch(t), die Fragen so ad hoc zu beantworten. Falls
> das nicht klappt, so sollte ein Skript
> oder so zur Hand genommen werden, dort dann konzentriert
> und gezielt das nachgeschaut werden, was
> zur Benatwortung der Frage notwendig ist.
Wo steht denn in unserem Skript etwas zur strukturellen Induktion?
> Pruefungslernen heisst vor allem Konzentration auf das
> Wesentliche und Trainieren der Intuition, damit
> man die Dinge geschickt und kompakt bei sich abspeichern
> kann und trotzdem nicht den Kopf total zu hat.
>
> Dies als nur einige wohlgemeinte
> Anmerkungen....
Jo - danke. 
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
> Hallo Mathias...
>
> > (1) Definiere die Klasse RE der regulären Ausdrücke über
> > dem Alphabet [mm]\{0,1\}[/mm]
> > (zB durch Angabe einer BNF). Definiere die semantische
> > Funktion [mm]\varphi\colon RE\to P(\{0,1\}^{\star}).[/mm]
>
> [mm](\{0,1\}\cup\{(,),+,^{\star}\}\cup\{\emptyset,\Lambda\},\{\},,r)[/mm]
> mit r:
>
> [mm]::=0|1|(+)|()^{\star}|()|\emptyset|\Lambda[/mm]
>
> [mm]\varphi\colon RE\to\cal{P}(\{0,1\}^{\star}):[/mm]
>
> [mm]\varphi(0)=0[/mm]
> [mm]\varphi(1)=1[/mm]
> [mm]\varphi(\emptyset)=\emptyset[/mm]
> [mm]\varphi(\Lambda)=\{\Lambda\}[/mm] (wieso muss denn hier eine
> Klammer drum?)
Darum !
Wieso muss denn um die 0 und die 1 keine ?
Im Ernst: Von wo nach wo bildet die semantische Funktion ab ? Zu jedem [mm] R\in [/mm] RE ist doch
[mm] \varphi (R)\in P(\{0,1\}^{\star}),
[/mm]
also [mm] \varphi (R)\subseteq\{0,1\}^{\star}.
[/mm]
Dann musst Du wohl auch
[mm] \varphi (0)=\{0\} [/mm] und so weiter schreiben, oder ?
Konzentration !!!
> [mm]\varphi(R_1+R_2)=\varphi(R_1)\cup\varphi(R_2)[/mm]
> [mm]\varphi(R_1R_2)=\varphi(R_1)\varphi(R_2)[/mm]
> [mm]\varphi(R_1^{\star})=(\varphi(R_1))^{\star}[/mm]
>
> für R, [mm]R_1, R_2 \in[/mm] RE
>
> > (2) Zeige: Zu jedem regulären Ausdruck R gibt es einen
> > äquivalenten NEA A, d.h. mit [mm]L(A)=\varphi[/mm] (R).
> > Hinweis dazu: Führe den Beweis durch strukturierte
> > Induktion über den Aufbau der reguláren Ausdrücke.
>
> Mmh - wie mach ich das denn?
>
Ähhh.... ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
... besprechen wir noch.
(Kurzform: Ind.Anf.: Fuer R=0, R=1, [mm] R=\emptyset, R=\Lambda [/mm] jeweils explizit NEA angeben, dann im Induktionsschritt
zB fuer [mm] R=(R_1+R_2) [/mm] annehmen, dass NEA [mm] A_i [/mm] fuer [mm] R_i [/mm] gegeben sind und beschreiben, wie man daraus einen
NEA fuer R konstruiert usw.......)
> > (3) Zeige umgekehrt: Zu jedem DEA A gibt es einen reg.
> > Ausdruck R mit [mm]\varphi[/mm] (R)=L(A).
>
> Hierfür müsste doch eigentlich folgendes reichen:
>
> Sei [mm](S,M,s_0,F)[/mm] ein DEA, dann definiere ich eine BNF
> folgendermaßen:
> für [mm]s\in F[/mm]: [mm]s\to\varepsilon[/mm]
> für [mm]M(s,\sigma)=p:[/mm] [mm]s\to\sigma p[/mm]
> für [mm]M(s,\sigma)=p\in F[/mm]:
> [mm]s\to\sigma.[/mm]
>
BNF reicht nicht. BNF sind - wie Dir im November im Forum jemand richtig
erklaert hat - kontextfrei, aber i.a. nicht regulär.
Ich sag nur: An einem vergangenen Freitag in HS 1.....
> Aber wie bringe ich das in Worte, was das mit der
> Aufgabenstellung zu tun hat?
>
> > Teil 2 einer kleinen, für einen ganz speziellen
> > Adressatenkreis geschriebenen Serie.
>
> Hat dieser Adressatenkreis vielleicht Mächtigkeit 1?
>
Das wäre zu testen....
> > Ein Hinweis allgemein, damit nicht Zeit durch etwaige
> > Schwierigkeiten verloren geht:
>
> Mmh - schneller ginge es doch so: ich kann mit der Aufgabe
> nichts anfangen, also lasse ich es bleiben...
>
Dann säßen wir heute noch in Höhlen und würden Steine kloppen....
> > - Versuch(t), die Fragen so ad hoc zu beantworten. Falls
> > das nicht klappt, so sollte ein Skript
> > oder so zur Hand genommen werden, dort dann
> konzentriert
> > und gezielt das nachgeschaut werden, was
> > zur Benatwortung der Frage notwendig ist.
>
> Wo steht denn in unserem Skript etwas zur strukturellen
> Induktion?
>
Es heißt ja: ''ein Skript oder so...''.
Im Skript steht dazu nichts. Sind ja auch nur Grundlagen.
Aber Beispiele zur SVI gibt es im Skript tonnenweise.
> > Pruefungslernen heisst vor allem Konzentration auf das
> > Wesentliche und Trainieren der Intuition, damit
> > man die Dinge geschickt und kompakt bei sich abspeichern
> > kann und trotzdem nicht den Kopf total zu hat.
> >
> > Dies als nur einige wohlgemeinte
> > Anmerkungen....
>
> Jo - danke.
>
> Viele Grüße
> Bastiane
>
>
Gruss,
Mathias
|
|
|
|
