Pumping Lemma in PDA und CFL

I eine Pump Lemmas Frage habe ich auf total stecken ...Pumping Lemma in PDA und CFL

L = {w ∈ {a, b, c} *: na (w) < nb (w) < nc (w)}

ist es CFL oder nicht?

Ich suche, es ist nicht CFL, weil es nicht genug ist, einen Stapel zu haben, um sich an alle diese Bedingungen zu erinnern. Sie können sich erinnern, dass na (w) < nb (w) oder na (w) < nc (w), nb (w) < nc (w) aber nicht na (w) < nb (w) < nc (w). Außerdem dachte ich, wenn die Sprache ein^pb^2pc^3p ist und dann wenn ich | vy | für p mal L ist nicht CF aber ist es möglich p für p mal hoch zu pumpen?

Oder irgendeine Idee für die Lösung?

Quelle

2012-04-02 erogol

ist das eine Hausaufgabe? es scheint wie ein direkter Beweis durch Widerspruch –

BTW, ich habe gerade zwei ähnliche Fragen gefunden: http://StackOverflow.com/Questions/4095509 und http://StackOverflow.com/Questions/4149357 –

Beachten Sie, dass Lemma Pumping in L jeder Zeichenfolge erfordert nach dem Pumpen in L zu bleiben. So ist es genug, um Widerspruch sogar für eine bestimmte Form von Strings in L zu bekommen.

ein ^p b ^2p c ^3p ist ein schönes Beispiel, aber ich schlage vor, eine kürzere, um zu versuchen: a ^p b ^{p + 1} c ^{p + 2}.

Die Begründung ist fast die gleiche wie in der Wikipedia-Artikel: Pumping lemma:Usage. Sie werden die gleichen fünf Fälle haben und es ist ziemlich einfach, in jedem einen Widerspruch zu bekommen.

Quelle

2012-04-02 21:40:25

Antwort

Verwandte Themen