Prouver qu'un langage de forme 0^n où n est premier n'est ni régulier ni contextuel

Question

Je pense à cela assez longtemps, mais je n'ai toujours pas pu aller loin. La première étape est facile en considérant n'importe quelle langue de forme où M est un premier plus grand que ce que notre adversaire a donné (disons n). Je ne suis pas capable de comprendre comment nous pouvons prouver d'ici que peu importe notre l'adversaire casse la corde que nous pouvons toujours pomper pour montrer qu'elle n'appartient pas à la classe des langages libres de contexte (et donc aux langages réguliers). PS: Ce n'est pas une question de devoirs.J'ai déjà terminé ce cours.J'essaie juste de le résoudre car je n'ai pas été capable de le résoudre pendant mon terme de cours.

Answer 1

Supposons que la langue donnée est sans contexte. En utilisant le pumping lemma for context-free languages, vous obtiendrez des nombres x et y tels que x, x + y, x + 2y, x + 3y, et ainsi de suite, sont tous des nombres premiers. Cependant, ce n'est pas possible, car il y a arbitrairement de grands espaces entre les nombres premiers (pour le prouver, considérons les nombres n! +2, n! +3, .... n! + N, pour tout nombre naturel n> = 2 - ils sont tous composites).

Une autre approche consiste à utiliser le théorème selon lequel tout langage sans contexte sur un alphabet unaire est un langage régulier. Ensuite, considérez comment les DFA peuvent ressembler à un alphabet unaire: chaque état a exactement un bord sortant. Après avoir éliminé les états inaccessibles, les états doivent être q_0, q_1, ... q_k, où la transition de q_i va à q_ {i + 1}, pour 1 < = i < k, et la transition de q_k à un état quelconque. q_0 est l'état initial. Indépendamment de l'ensemble des états finaux choisis, ceci ne peut pas accepter {0^n | n est un nombre premier} - encore une fois, utilisez le fait qu'il existe des espaces arbitrairement grands entre les nombres premiers pour obtenir une contradiction.