reguläre Grammatik < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:41 So 23.11.2008 | | Autor: | chriz123 |
| Aufgabe | Lassen sich mit Grammatiken, die nur Produktionen der Form A [mm] \to [/mm] a, A [mm] \to [/mm] Ba, A [mm] \to [/mm] aB und A [mm] \to \varepsilon [/mm] enthalten, auch nicht-reguläre Sprachen erzeugen?
Begründen Sie Ihre Antwort. |
Ich würde sagen: Ja.
Aber mit der Begründung tue ich mich schwer.
Was mich verwirrt ist, das aus der Variable B gar keine Ableitungen gebildet werden können.
Somit enthällt die Sprache doch nur die Wörter a und [mm] \varepsilon [/mm] oder??
Oder ist das einfach allgemein gemeint?
So das die Regeln entweder ein Terminalsymbol, eine Variable und ein Terminalsymbol oder Epsilon auf der rechten Seite enthalten??
Das klingt zwar logisch, aber ich weiß nicht womit ich dann argumentieren soll.
Meine Idee:
G ist kontextfrei, falls für alle Regeln
u [mm] \to [/mm] v gilt: u [mm] \in [/mm] V.
Das stimmt mit den Regeln von oben überein oder??
Kann mir da jemand weiterhelfen??
Vielen Dank!
Chriz123
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:07 So 23.11.2008 | | Autor: | uliweil |
> Lassen sich mit Grammatiken, die nur Produktionen der Form
> A [mm]\to[/mm] a, A [mm]\to[/mm] Ba, A [mm]\to[/mm] aB und A [mm]\to \varepsilon[/mm]
> enthalten, auch nicht-reguläre Sprachen erzeugen?
> Begründen Sie Ihre Antwort.
> Ich würde sagen: Ja.
> Aber mit der Begründung tue ich mich schwer.
>
> Was mich verwirrt ist, das aus der Variable B gar keine
> Ableitungen gebildet werden können.
> Somit enthällt die Sprache doch nur die Wörter a und
> [mm]\varepsilon[/mm] oder??
>
nein!
> Oder ist das einfach allgemein gemeint?
ja! Es heißt ja: Regeln der Form ...
> So das die Regeln entweder ein Terminalsymbol, eine
> Variable und ein Terminalsymbol oder Epsilon auf der
> rechten Seite enthalten??
ja
> Das klingt zwar logisch, aber ich weiß nicht womit ich
> dann argumentieren soll.
>
> Meine Idee:
> G ist kontextfrei, falls für alle Regeln
> u [mm]\to[/mm] v gilt: u [mm]\in[/mm] V.
> Das stimmt mit den Regeln von oben überein oder??
richtig: Grammatiken, die nur Regeln der angegebenen Form enthalten, sind kontextfrei. Aber alle regulären Sprachen sind auch kontextfrei und hier ist die Frage, ob man mit einer Grammatik dieser Form auch eine (zwar kontextfreie, aber) nicht-reguläre Sprachen erzeugen kann.
Die Frage ist also: kann man mit Grammatiken der angegebenen Form nicht nur reguläre Sprachen, sondern auch nicht-reguläre erzeugen?
>
> Kann mir da jemand weiterhelfen??
Du solltest mal nachlesen, was reguläre Sprachen sind und von welchen Grammtiken sie erzeugt werden.
Dann solltest du dich für eine Antwort entscheiden (du hast ja schon "ja" vermutet) und versuchen, deine Antwort zu beweisen.
Wenn du bei "ja" bleibst ("ja, man kann auch nicht-reguläre Sprachen erzeugen"), reicht es zum Beweis, eine Sprache zu finden, von der du weißt, dass sie nicht regulär ist, sich aber von einer Grammatik dieser Form erzeugen lässt.
Wenn du dich für "nein" entscheidest, müsstest du beweisen, dass jede Sprache, die von einer solchen Grammatik erzeugt wird, regulär ist.
>
> Vielen Dank!
> Chriz123
Beste Grüße
uliweil
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:09 So 23.11.2008 | | Autor: | bazzzty |
> Lassen sich mit Grammatiken, die nur Produktionen der Form
> A [mm]\to[/mm] a, A [mm]\to[/mm] Ba, A [mm]\to[/mm] aB und A [mm]\to \varepsilon[/mm]
> enthalten, auch nicht-reguläre Sprachen erzeugen?
> Was mich verwirrt ist, das aus der Variable B gar keine
> Ableitungen gebildet werden können.
> Somit enthällt die Sprache doch nur die Wörter a und
> [mm]\varepsilon[/mm] oder??
>
> Oder ist das einfach allgemein gemeint?
Ja. Die Frage ist, ob man, wenn man Produktionen erlaubt, die
Nichtterminale auf Terminal-Nichtterminal- und auf Nichtterminal/Terminal-Kombinationen abbilden, auch nicht-reguläre Sprachen erzeugen kann.
> Meine Idee:
> G ist kontextfrei, falls für alle Regeln
> u [mm]\to[/mm] v gilt: u [mm]\in[/mm] V.
> Das stimmt mit den Regeln von oben überein oder??
Das wird Dir nicht viel bringen. Entweder Du zeigst, daß Du jede Grammatik, die so gebaut ist wie oben beschrieben, ersetzen kannst durch eine reguläre Grammatik, oder Du zeigst, daß es eine nicht-reguläre Sprache gibt, die Du mit so einer Grammatik beschreiben kannst.
Mach Dir klar, warum das die beiden Möglichkeiten sind! Zu wissen, was man beweisen muß, um was zu zeigen, ist of schon die halbe Miete.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:23 Mo 24.11.2008 | | Autor: | chriz123 |
Ups da hab ich n bisschen was durcheinander gehauen...
Also jetzt würde ich sagen, mit der gegebenen Definition lassen sich nur reguläre Sprachen erzeugen.
Da reguläre Sprachen von regulären Grammatiken erzeugt werden und die obige Definition genau die Definition der regulären Grammatik ist.
Dadurch ist das doch schon klar oder??
Obwohl es mir ganz schön einfach vorkommt.
Aber wir sollten das ja auch nur begründen und nicht beweisen...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:26 Mo 24.11.2008 | | Autor: | bazzzty |
> Ups da hab ich n bisschen was durcheinander gehauen...
>
> Also jetzt würde ich sagen, mit der gegebenen Definition
> lassen sich nur reguläre Sprachen erzeugen.
> Da reguläre Sprachen von regulären Grammatiken erzeugt
> werden und die obige Definition genau die Definition der
> regulären Grammatik ist.
Das stimmt nicht. Reguläre Sprachen werden von regulären Grammatiken erzeugt, ja. Aber reguläre Grammatiken sind entweder linksregulär oder rechtsregulär und lassen nur eine der beiden Produktionstypen [mm]A\to aB[/mm] oder [mm]A\to Ba[/mm] zu. Die Frage ist: Wenn man diese Einschränkung fallenläßt, kann man dann mehr erzeugen als mit dieser Einschränkung
|
|
|
|
