Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
flixgott Gast
|
Verfasst am: 27. Apr 2005 17:31 Titel: formale sprachen |
|
|
hallo, da ich mit dem matheboard schon sehr gute erfahrungen gemacht habe, hoffe ich jetzt hier auch die ein oder andere lösungshilfe zu bekommen (und selbst vielleicht auch hilfestellungen zu geben)
nun zu meiner frage:
ich habe ein einbuchstabiges alphabet A={a} nun will ich mit diesem folgende sprache erzeugen:
L enthält also alle wörter, die nur aus dem buchstaben a bestehen und dieser dort 2^n mal auftritt.
ich will jetzt gerne wissen, was für eine sprache das ist.
ich vermute stark, dass sie nicht kontextfrei ist (allerdings kann ich das nicht wirklich beweisen, ich finde nur keine kontextfreie grammtik)
ich bin mir sicher, dass es eine rekursive bzw entscheidbare sprache ist, denn eine turingmaschine, die diese sprache erkennt könnte ich wahrscheinlich konstruieren.
nun würde ich gern wissen, ob sie kontextsensitiv ist und warum das so. ich hab überhaupt keine idee, wie ich da ran gehen soll!
danke für jede hilfestellung! |
|
Nach oben |
|
|
|
kurellajunior Administrator
Anmeldungsdatum: 14.02.2005 Beiträge: 214 Wohnort: Berlin-Pankow
|
Verfasst am: 28. Apr 2005 12:50 Titel: |
|
|
Zeig doch mal deine Kontextsensitive Grammatik. Aus dem Stand finde ich ja nichtmal so eine.
Jan
Erstmal die Sprache:
Für Kontextfreiheit muss gelten:
Sei dann gibt es so dass gilt:-
-
nehmen das Wort
Aus 1. folgt... Du bist dran _________________
|
|
Nach oben |
|
|
Remington Steele
Anmeldungsdatum: 04.06.2005 Beiträge: 31
|
Verfasst am: 14. Aug 2005 23:35 Titel: |
|
|
Bin ich es oder sind die Latex-Codierungen total falsch. Ich kann leider gar nicht lesen, was da stehen soll . Mich würde das Thema auch interessieren, könntet Ihr das evtl. für mich editieren? Thx... |
|
Nach oben |
|
|
ED209
Anmeldungsdatum: 30.05.2005 Beiträge: 122
|
Verfasst am: 15. Aug 2005 02:00 Titel: |
|
|
ich seh auch nur fehlermeldungen _________________ +++++++++++++[>++++>+<<-]>.--.>---. |
|
Nach oben |
|
|
Paul_H
Anmeldungsdatum: 01.02.2006 Beiträge: 52 Wohnort: Bonn
|
Verfasst am: 13. März 2006 17:43 Titel: |
|
|
Also, man könnte diese Sprache mit folgender Grammatik beschreiben:
G = ( {A}, {a}, P, A) mit P:
A --> AA | aa.
Diese Grammatik ist kontextfrei.
Oder hab ich hier etwas total falsch verstanden??? |
|
Nach oben |
|
|
Tobias
Anmeldungsdatum: 15.02.2005 Beiträge: 149
|
Verfasst am: 13. März 2006 18:45 Titel: |
|
|
G = ( {A}, {a}, P, A) mit P:
A --> AA | aa.
A --> AA --> AAA --> aaaaaa = a^6
6 ist keine 2er Potenz.
kurellajunior hat schon den Ansatz gezeigt, wie man die Sprache weiter einordnen kann: Pumpinglemma. Damit kannst du widerlegen, dass die Sprache kontextfrei ist.
Eine entscheidbare Sprache ist es auf jeden Fall. Idee:
Zähle a's binär und schaue, ob in dem Binärcode der Summe nur eine 1 vorkommt. |
|
Nach oben |
|
|
|