lemme de pompage dans PDA et CFL

J'ai une question lemme de pompage Je suis totalement bloqué sur ...lemme de pompage dans PDA et CFL

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

est-ce que c'est CFL ou non?

Je doute que ce ne soit pas la LCF, car il ne suffit pas d'avoir une pile pour se souvenir de ces conditions. Vous pouvez vous rappeler que na (w) < nb (w) ou na (w) < nc (w), nb (w) < nc (w) mais pas na (w) < nb (w) < nc (w). En plus je pense que si la langue est un^pb^2pc^3p et que si je pompais | vy | pour p fois L n'est pas CF cependant est-il possible de pomper p fois?

Ou une idée pour la solution?

Source

2012-04-02 erogol

Est-ce un devoir? il semble comme une preuve directe par la contradiction –

btw, je viens de trouver deux questions similaires: http://stackoverflow.com/questions/4095509 et http://stackoverflow.com/questions/4149357 –

Notez que le lemme de pompage nécessite chaque chaîne dans L de rester dans L après le pompage. Donc, il suffit d'obtenir une contradiction même pour une forme spécifique de chaînes dans L.

un ^p b c 2p 3p est un bel exemple, mais je suggère d'essayer une plus courte: une ^p b ^{p + 1 c}^{p + 2}.

Le raisonnement est presque le même que dans l'article de Wikipedia: Pumping lemma:Usage. Vous aurez les mêmes cinq cas et il est assez simple d'obtenir une contradiction dans chacun d'eux.

Source

2012-04-02 21:40:25

lemme de pompage dans PDA et CFL

Répondre

Questions connexes