kontextfreie Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Konstruieren Sie eine kontextfreie Grammatik für die folgenden Sprachen über dem Alphabet [mm] \summe [/mm] = {0,1}:
a) L = { [mm] 1^n0^m [/mm] | m,n [mm] \in \IN_{0}, [/mm] m < n }
b) L = {w [mm] \in \summe [/mm] * | [mm] |w|_0 [/mm] = 2 [mm] |w|_1 [/mm] }
c) L = {w [mm] \in \summe [/mm] * | w ist Palindrom} |
Miau :3
ich hab seit diesem Semster "Grundlagen der theoretischen Informatik" als Nebenfach, habe aber keine Vorkenntnisse (nur als Vorwahnung ;))
bei dieser Aufgabe fehlen mir irgendwie die Ideen zur Aufgabe b und c
bei der Aufgabe a) habe ich für die Grammatik G = { [mm] V,\summe [/mm] , P,S }
für V = {S,A,B,C,D} und
[mm] P=\begin{cases} S \to C \\ A\to 11 \\ A \to 1D \\ B \to \epsilon \\ C \to AB \\C \to 1C0 \\ D\to \epsilon \\ D\to 1D \end{cases}
[/mm]
kann man das irgendwie überprüfen?
bei der b und der c hab ich wie gesagt noch keine Idee, kann mir vielleicht einer sagen, wie ich da ran gehen kann?
Liebe Grüße
Katze :3
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:26 Do 21.04.2011 | | Autor: | felixf |
Miau!
> Konstruieren Sie eine kontextfreie Grammatik für die
> folgenden Sprachen über dem Alphabet [mm]\summe[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= {0,1}:
> a) L = { [mm]1^n0^m[/mm] | m,n [mm]\in \IN_{0},[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
m < n }
> b) L = {w [mm]\in \summe[/mm] * | [mm]|w|_0[/mm] = 2 [mm]|w|_1[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
Ist $|w|_0$ die Anzahl der Nullen in $w$?
> c) L = {w [mm]\in \summe[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
* | w ist Palindrom}
>
> Miau :3
> ich hab seit diesem Semster "Grundlagen der theoretischen
> Informatik" als Nebenfach, habe aber keine Vorkenntnisse
> (nur als Vorwahnung ;))
>
> bei dieser Aufgabe fehlen mir irgendwie die Ideen zur
> Aufgabe b und c
>
> bei der Aufgabe a) habe ich für die Grammatik G = {
> [mm]V,\summe[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
, P,S }
> für V = {S,A,B,C,D} und
> [mm]P=\begin{cases} S \to C \\ A\to 11 \\ A \to 1D \\ B \to \epsilon \\ C \to AB \\C \to 1C0 \\ D\to \epsilon \\ D\to 1D \end{cases}[/mm]
Das stimmt schon, aber das ist unnoetig kompliziert.
Du kannst mit $V = [mm] \{ S \}$ [/mm] und mit drei Regeln in $P$ auskommen. Versuch mal $P$ fuer $V = [mm] \{ S \}$ [/mm] zu finden.
> bei der b und der c hab ich wie gesagt noch keine Idee,
> kann mir vielleicht einer sagen, wie ich da ran gehen
> kann?
Bei c) hilft dir vielleihct folgende Umschreibung weiter:
* [mm] $\epsilon$, [/mm] $0$ und $1$ sind Palindrome
* ist $w$ ein Palindrom, so auch $0 w 0$ und $1 w 1$
* jedes Paldindrom kann damit erreicht werden
Zu b) habe ich grad keine gute Idee.
LG Felix
|
|
|
| |
|
wieso einfach wenn es auch kompliziert geht :3
bin gerade bei
[mm] P=\begin{cases} S\to 1S0 \\ S\to 1S \\ S\to 1 \end{cases}
[/mm]
mit der ersten kann ich die Anzahl der Nullen bestimmen, mit der zweiten dann die anzahl der Einser und mit der letzten gehe ich sicher, dass es mindestens eine Eins mehr gibt als die Null
bei der c) komm ich leider nicht weiter
komme zwar auf P für aya für [mm] a\in [/mm] {0,1}, [mm] y\in (\summe)*
[/mm]
P [mm] =\begin{cases} S \to aA \\ A \to a \\ A \to 0A \\ A \to 1A \end{cases}
[/mm]
aber wie ich für y (also endlich viele Symbole) auch eine Ordnung hinbekomme weiß ich gerade nicht
obwohl ich gerade bei dem bin
P [mm] =\begin{cases} S \to C \\C \to a \\ C \to A \\ A \to bBb \\ A \to aAa \\ B\to bBb \\ B\to aAa \\A \to \epsilon \\ B \to \epsilon \end{cases}
[/mm]
für a,b [mm] \in [/mm] {0,1} [mm] a\not=b
[/mm]
LG
Katze :3
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Sa 23.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Sa 23.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
