Informatiker Board | Druckvorschau: Aufgabe Spracharithmetik

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Aufgabe Spracharithmetik (http://www.informatikerboard.de/board/thread.php?threadid=401)

Geschrieben von newsys am 10.04.2008 um 21:31:

Aufgabe Spracharithmetik

Hallo allerseits,

ich habe eine Aufgabe und weiß nicht wie ich daran gehen soll. Wir haben erst 2 Vorlesungen gehört und der Prof ist nicht auf die Themen der Aufgaben eingegangen. Hier erstmal die Aufgabe:

In dieser Aufgabe betrachten wir eine Unterfamilie von formalen Sprachen über einem Alphabet, die wir RA-Sprachen nennen wollen und die wie folgt definiert sind:
• Die leere Menge ist eine RA-Sprache.
• Die Menge {epsilon} für das leere Wort epsilon element Sigma* ist eine RA-Sprache.
• Für jedes a element Sigma ist {a} eine RA-Sprache
• Wenn R und S RA-Sprachen sind, so auch R u S, R ° S (auch RS geschrieben) und
R* Nur die durch endliche Anwendung der obigen Regeln gebildeten Sprachen sind RASprachen.

Gegeben sei das Alphabet {0, 1}. Zeigen Sie, dass folgende formale Sprachen über dem Alphabet Sigma ={0, 1} RA-Sprachen sind:
1. {epsilon, 0}
2. {w beginnt mit einer 1 und endet mit einer 0}
3. {w enthält eine gerade Anzahl an Nullen oder genau eine 1}
4. {w hat eine führende 1 und gerade Länge oder w hat eine führende 0 und
ungerade Länge}

Wie gehe ich an diese Aufgabe heran?

Geschrieben von Tobias am 11.04.2008 um 11:27:

Hallo,

wenn ich es richtig überblicke, sind hier gerade die Regeln zur Bildung von Regulären Sprachen (RA = regulärer Ausduck?) angegeben.

Du musst hier streng nach den formulierten Regeln deine Sprachmengen konstruieren.

1.) Ist ganz einfach und sollte dir eigentlich sofort gelingen.

2.) Das will ich einmal vormachen:

Sei L = {w beginnt mit einer 1 und endet mit einer 0}. Wir wollen zeigen, dass $[latex]L \in \operatorname{RA}[/latex]$ . Dafür kann man L auch so schreiben:
$[latex]L = \{1w0 \mid w \in \Sigma^\ast\} = \{1\}\cdot \Sigma^\ast \cdot \{0\}[/latex]$ .

Wir betrachten folgende Regeln:
$[latex]\{0\} \in \operatorname{RA}[/latex]$ wegen $[latex]0 \in \Sigma[/latex]$
$[latex]\{1\} \in \operatorname{RA}[/latex]$ wegen $[latex]1 \in \Sigma[/latex]$
$[latex]\Sigma \in \operatorname{RA}[/latex]$ wegen $[latex]\Sigma = \{0\} \cup \{1\}[/latex]$ und $[latex]\{0\}, \{1\} \in \operatorname{RA}[/latex]$
$[latex]\Sigma^\ast \in \operatorname{RA}[/latex]$ wegen $[latex]\Sigma \in \operatorname{RA}[/latex]$
$[latex] \{1\}\cdot \Sigma^\ast \in \operatorname{RA}[/latex]$ wegen $[latex]\{1\}, \Sigma^\ast \in \operatorname{RA}[/latex]$
$[latex]L = \{1\}\cdot \Sigma^\ast\cdot \{0\} \in \operatorname{RA}[/latex]$ wegen $[latex]\{1\}\cdot\Sigma^\ast, \{0\} \in \operatorname{RA}[/latex]$

Zitat:

Wir haben erst 2 Vorlesungen gehört und der Prof ist nicht auf die Themen der Aufgaben eingegangen.

Willkommen an der Uni. Augenzwinkern

Geschrieben von newsys am 12.04.2008 um 12:39:

ok das habe ich soweit verstanden. Aber ich habe noch Probleme mit der Anzahl. In Mathe würde ich jetzt einfach für eine gerade Anzal 2n nehmen und für eine ungerade 2n+1 aber wie mache ich hier.

zB für die aufgabe {w enthält eine gerade Anzahl an Nullen oder genau eine 1}

L = ???? v {1}

Geschrieben von Tobias am 12.04.2008 um 13:46:

Der Trick ist jeweils die Menge so darzustellen, dass man die vorgegebenen Operatoren sofort erkennt. Ein "oder" in deiner Formulierung weist z.B. auf eine Vereinigung hin.

Man kann also L = {w enthält eine gerade Anzahl an Nullen oder genau eine 1} so schreiben:
$[latex]L = X \cup Y[/latex]$

X = {w enthält eine gerade Anzahl an Nullen }
Y = {w enthält genau eine 1}

Y ist recht einfach zu modellieren. Wie sehen alle Worte aus, die genau eine 1 enthalten?

X ist etwas kniffliger. Eine Idee ist, jedes Wort aus X so aufzuteilen, dass jedes Teilwort GENAU zwei 0en enthält. Wenn man solche Teilwörter konkateniert, erhält man zwangsläufig ein Wort mit gerade vielen 0en. Man erhält also für die Teilwörter eine Menge $[latex]T = \{1\}^\ast \cdot \{0\} \cdot \{1\}^\ast \cdot \{0\} \cdot \{1\}^\ast[/latex]$ . Konkateniert man beliebig viele Wörter aus T (also T*) hat man fast die Menge X. Was noch fehlt ist die Möglichkeit, dass X garkeine 0en (0 ist auch eine gerade Zahl) enthält.

Geschrieben von newsys am 13.04.2008 um 11:48:

Ok - das sollte ich so hinbekommen. Schonmla vielen Dank.

Jetzt habe ich noch eine Frage und zwar wie man an diese Aufgabe rangeht:

Erstellen Sie für jede der folgenden Sprachen über dem Alphabet = {0, 1} eine kontextfreie
Grammatik und begründen Sie informal, dass Ihre Grammatik tatsächlich die Sprache
erzeugt.
1. {w ∈ | w enthält mindestens eine 1}
2. {w ∈ | w beginnt und endet mit demselben Symbol}

Genauso wie an Aufgabe 1??????? Oder muss man da noch Produktionsregeln finden???