Zum neuen Informatik-Forum >>
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

formale sprachen

 
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
flixgott
Gast





BeitragVerfasst am: 27. Apr 2005 17:31    Titel: formale sprachen Antworten mit Zitat

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

BeitragVerfasst am: 28. Apr 2005 12:50    Titel: Antworten mit Zitat

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 Augenzwinkern

_________________
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Remington Steele



Anmeldungsdatum: 04.06.2005
Beiträge: 31

BeitragVerfasst am: 14. Aug 2005 23:35    Titel: Antworten mit Zitat

Bin ich es oder sind die Latex-Codierungen total falsch. Ich kann leider gar nicht lesen, was da stehen soll unglücklich. Mich würde das Thema auch interessieren, könntet Ihr das evtl. für mich editieren? Thx...
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
ED209



Anmeldungsdatum: 30.05.2005
Beiträge: 122

BeitragVerfasst am: 15. Aug 2005 02:00    Titel: Antworten mit Zitat

ich seh auch nur fehlermeldungen
_________________
+++++++++++++[>++++>+<<-]>.--.>---.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
Paul_H



Anmeldungsdatum: 01.02.2006
Beiträge: 52
Wohnort: Bonn

BeitragVerfasst am: 13. März 2006 17:43    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
Tobias



Anmeldungsdatum: 15.02.2005
Beiträge: 149

BeitragVerfasst am: 13. März 2006 18:45    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
Beiträge der letzten Zeit anzeigen:   
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum nicht posten
Du kannst Dateien in diesem Forum nicht herunterladen