Elimination unnützer Variablen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 09:48 So 05.01.2014 | | Autor: | DrRiese |
| Aufgabe | Geben Sie für die folgenden Grammatiken solche an, die keine unnützen Variablen enthalten und dieselbe Sprache erzeugen:
a) [mm] G_{1}:=(\{S,A,B,C\},\{a,b\},P_{1},S), [/mm] wobei
[mm] P_{1}:=\{S \rightarrow AB, S \rightarrow CA, A \rightarrow a, B \rightarrow BC, B \rightarrow AB, C \rightarrow aB, C \rightarrow b \} [/mm]
b) [mm] G_{2}:=(\{S,A,B,C,D,E\},\{a,b,c\},P_{2},S), [/mm] wobei
[mm] P_{2}:=\{S \rightarrow \epsilon, S \rightarrow aAa, S \rightarrow aa, S \rightarrow bBb, S \rightarrow bb, A \rightarrow C, A \rightarrow a, B \rightarrow C, B \rightarrow b, C \rightarrow DE, C \rightarrow CDE, C \rightarrow E, C \rightarrow CE, D \rightarrow A, D \rightarrow B, D \rightarrow ab\}. [/mm] |
Hallo 
Habe diese Aufgabe bearbeitet und würde mich sehr über eine kleine Korrektur freuen
a)
Kann man dann einfach schreiben:
Elimination von B, da B nicht terminiert, also
S [mm] \rightarrow [/mm] CA
A [mm] \rightarrow [/mm] a
C [mm] \rightarrow [/mm] b
b)
Hier müsste doch die Lösung sein:
Elimination von E, da keine Ableitung für E enthalten
Deshalb Elimination von C.
Deshalb Elimination von D, da nicht mehr erreichbar.
Also:
S [mm] \rightarrow \epsilon [/mm] | aAa| aa| bBb| bb
A [mm] \rightarrow [/mm] a
B [mm] \rightarrow [/mm] b
Wäre das so i.O.?
LG,
DrRiese
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:37 Mo 06.01.2014 | | Autor: | DrRiese |
Keiner da, der kurz drüberguckt? :-(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:19 Di 07.01.2014 | | Autor: | DrRiese |
Niemand da, der kurz Zeit hat? :-(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Do 09.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
