Informatiker Board | formale Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Wortmenge L

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Wortmenge L

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Lisa23
Grünschnabel

Dabei seit: 19.10.2011
Beiträge: 7

Wortmenge L

Zitatantwort auf diesen Beitrag erstellen

Kann mir bitte jemand sagen wie ich so eine Aufgabe angehen muss wie man diese Wortmenge lesen würde.
Ich hab bei wikipedia gelesen das Kontextfreie Grammatiken als Regel immer
A--->a
B--->aAa
D--->z

haben also das links immer ein Nichtterminierendes Symbol alleine steht.
und das das bei Kontextsensitiven Grammatiken es auch immer ein Nichtterminierendes Symbol links vom Pfeil sein muss aber das da auch 2 stehen dürfen oder eines.

Mfg
Lisa

Lisa23 hat dieses Bild (verkleinerte Version) angehängt:

14.03.2012 12:12

Nehmen Sie Lisa23 in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

das beste ist meist, wenn man Dinge, die man schon kennt wiederverwendet smile

Du kennst ja bereits eine Grammatik für die Sprache [latex]a^nb^n[/latex]

Noch ein kleiner Tipp:

$[latex] a^nb^{n+m}a^m = (a^nb^n)(b^ma^m)[/latex]$

Und nun nur noch ein wenig Lego smile

(Hab auch 15-30 min gebraucht)

Zum Nachweis:
für Kontextfreie Sprachen gilt, dass ein Kellerautomat angebbar sein muss. Hier kann einer angegeben werden der folgendermaßen funktioniert:
- Lege Elemente auf den Keller solange a gelesen werden.
- Entferne Elemente vom Keller solage b gelesen werden und Kellerstartsymbol nicht erreicht ist
- Bei erreichen des Kellerstartsymbols, lege neue Kellersymbole auf den Keller, solange b gelesen wird
- Lösche Kellersymbole, solange a gelesen wird.
- Akzeptiere wenn eingabe = epsilon und Kellerstartsymbol auf dem Keller...

Wobei es schwierig sein kann, einen solchen Automaten anzugeben. Der Nachweis, dass eine Sprache definitiv nicht Kontextfrei ist, lässt sich über das Pumping-Lemma für Kontextfreie Sprachen führen.

VG,

Karlito

14.03.2012 20:05

Nehmen Sie Karlito in Ihre Freundesliste auf

Lisa23
Grünschnabel

Dabei seit: 19.10.2011
Beiträge: 7

wieso kenne ich bereit eine sprache für a^n*b^n
ich weiss gar nicht was damit gemeint ist kannst du mir das bisschen näher erklären.

14.03.2012 20:43

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo Lisa,

ich dachte du hättest die Sprache anhand deiner anderen Frage bereits erkannt.

Es kann natürlich sein, dass ihr Kellerautomaten noch nicht hattet. Dann vergiss einfach was ich darüber geschrieben habe. Was den Nachweis der Nichterkennbarkeit angeht, kenne ich keine andere Methode.

Ich denke jetzt sollte es klarer sein, oder?

VG,

Karlito

14.03.2012 21:11

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Wortmenge L